MIPS64: r6 compact branch optimization.

src/mips64/assembler-mips64.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 393 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.
+
+  enum OffsetSize : int { kOffset26 = 26, kOffset21 = 21, kOffset16 = 16 };
+
   // 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);
+  bool is_near(Label* L, OffsetSize bits);
+  bool is_near_branch(Label* L);
+  inline bool is_near_pre_r6(Label* L) {
+    DCHECK(!(kArchVariant == kMips64r6));
+    return pc_offset() - L->pos() < kMaxBranchOffset - 4 * kInstrSize;
+  }
+  inline bool is_near_r6(Label* L) {
+    DCHECK(kArchVariant == kMips64r6);
+    return pc_offset() - L->pos() < kMaxCompactBranchOffset - 4 * kInstrSize;
+  }
+
+  int BranchOffset(Instr instr);
 
   // 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 branch_offset_compact(Label* L, bool jump_elimination_allowed);
-  int32_t branch_offset21(Label* L, bool jump_elimination_allowed);
-  int32_t branch_offset21_compact(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);
-    DCHECK((o & 3) == 0);   // Assert the offset is aligned.
-    return o >> 2;
+  int32_t branch_offset_helper(Label* L, OffsetSize bits);
+  inline int32_t branch_offset(Label* L) {
+    return branch_offset_helper(L, OffsetSize::kOffset16);
   }
-  int32_t shifted_branch_offset_compact(Label* L,
-      bool jump_elimination_allowed) {
-    int32_t o = branch_offset_compact(L, jump_elimination_allowed);
-    DCHECK((o & 3) == 0);   // Assert the offset is aligned.
-    return o >> 2;
+  inline int32_t branch_offset21(Label* L) {
+    return branch_offset_helper(L, OffsetSize::kOffset21);
+  }
+  inline int32_t branch_offset26(Label* L) {
+    return branch_offset_helper(L, OffsetSize::kOffset26);
+  }
+  inline int32_t shifted_branch_offset(Label* L) {
+    return branch_offset(L) >> 2;
+  }
+  inline int32_t shifted_branch_offset21(Label* L) {
+    return branch_offset21(L) >> 2;
+  }
+  inline int32_t shifted_branch_offset26(Label* L) {
+    return branch_offset26(L) >> 2;
   }
   uint64_t jump_address(Label* L);
   uint64_t jump_offset(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);
@@ skipping 120 matching lines @@
   void nop(unsigned int type = 0) {
     DCHECK(type < 32);
     Register nop_rt_reg = (type == 0) ? zero_reg : at;
     sll(zero_reg, nop_rt_reg, type, true);
   }
 
 
   // --------Branch-and-jump-instructions----------
   // We don't use likely variant of instructions.
   void b(int16_t offset);
-  void b(Label* L) { b(branch_offset(L, false)>>2); }
+  inline void b(Label* L) { b(shifted_branch_offset(L)); }
   void bal(int16_t offset);
-  void bal(Label* L) { bal(branch_offset(L, false)>>2); }
+  inline void bal(Label* L) { bal(shifted_branch_offset(L)); }
   void bc(int32_t offset);
-  void bc(Label* L) { bc(branch_offset(L, false) >> 2); }
+  inline void bc(Label* L) { bc(shifted_branch_offset26(L)); }
   void balc(int32_t offset);
-  void balc(Label* L) { balc(branch_offset(L, false) >> 2); }
+  inline void balc(Label* L) { balc(shifted_branch_offset26(L)); }
 
   void beq(Register rs, Register rt, int16_t offset);
-  void beq(Register rs, Register rt, Label* L) {
-    beq(rs, rt, branch_offset(L, false) >> 2);
+  inline void beq(Register rs, Register rt, Label* L) {
+    beq(rs, rt, shifted_branch_offset(L));
   }
   void bgez(Register rs, int16_t offset);
   void bgezc(Register rt, int16_t offset);
-  void bgezc(Register rt, Label* L) {
-    bgezc(rt, branch_offset_compact(L, false)>>2);
+  inline void bgezc(Register rt, Label* L) {
+    bgezc(rt, shifted_branch_offset(L));
   }
   void bgeuc(Register rs, Register rt, int16_t offset);
-  void bgeuc(Register rs, Register rt, Label* L) {
-    bgeuc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bgeuc(Register rs, Register rt, Label* L) {
+    bgeuc(rs, rt, shifted_branch_offset(L));
   }
   void bgec(Register rs, Register rt, int16_t offset);
-  void bgec(Register rs, Register rt, Label* L) {
-    bgec(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bgec(Register rs, Register rt, Label* L) {
+    bgec(rs, rt, shifted_branch_offset(L));
   }
   void bgezal(Register rs, int16_t offset);
   void bgezalc(Register rt, int16_t offset);
-  void bgezalc(Register rt, Label* L) {
-    bgezalc(rt, branch_offset_compact(L, false)>>2);
+  inline void bgezalc(Register rt, Label* L) {
+    bgezalc(rt, shifted_branch_offset(L));
   }
   void bgezall(Register rs, int16_t offset);
-  void bgezall(Register rs, Label* L) {
-    bgezall(rs, branch_offset(L, false)>>2);
+  inline void bgezall(Register rs, Label* L) {
+    bgezall(rs, branch_offset(L) >> 2);
   }
   void bgtz(Register rs, int16_t offset);
   void bgtzc(Register rt, int16_t offset);
-  void bgtzc(Register rt, Label* L) {
-    bgtzc(rt, branch_offset_compact(L, false)>>2);
+  inline void bgtzc(Register rt, Label* L) {
+    bgtzc(rt, shifted_branch_offset(L));
   }
   void blez(Register rs, int16_t offset);
   void blezc(Register rt, int16_t offset);
-  void blezc(Register rt, Label* L) {
-    blezc(rt, branch_offset_compact(L, false)>>2);
+  inline void blezc(Register rt, Label* L) {
+    blezc(rt, shifted_branch_offset(L));
   }
   void bltz(Register rs, int16_t offset);
   void bltzc(Register rt, int16_t offset);
-  void bltzc(Register rt, Label* L) {
-    bltzc(rt, branch_offset_compact(L, false)>>2);
+  inline void bltzc(Register rt, Label* L) {
+    bltzc(rt, shifted_branch_offset(L));
   }
   void bltuc(Register rs, Register rt, int16_t offset);
-  void bltuc(Register rs, Register rt, Label* L) {
-    bltuc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bltuc(Register rs, Register rt, Label* L) {
+    bltuc(rs, rt, shifted_branch_offset(L));
   }
   void bltc(Register rs, Register rt, int16_t offset);
-  void bltc(Register rs, Register rt, Label* L) {
-    bltc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bltc(Register rs, Register rt, Label* L) {
+    bltc(rs, rt, shifted_branch_offset(L));
   }
-
   void bltzal(Register rs, int16_t offset);
   void blezalc(Register rt, int16_t offset);
-  void blezalc(Register rt, Label* L) {
-    blezalc(rt, branch_offset_compact(L, false)>>2);
+  inline void blezalc(Register rt, Label* L) {
+    blezalc(rt, shifted_branch_offset(L));
   }
   void bltzalc(Register rt, int16_t offset);
-  void bltzalc(Register rt, Label* L) {
-    bltzalc(rt, branch_offset_compact(L, false)>>2);
+  inline void bltzalc(Register rt, Label* L) {
+    bltzalc(rt, shifted_branch_offset(L));
   }
   void bgtzalc(Register rt, int16_t offset);
-  void bgtzalc(Register rt, Label* L) {
-    bgtzalc(rt, branch_offset_compact(L, false)>>2);
+  inline void bgtzalc(Register rt, Label* L) {
+    bgtzalc(rt, shifted_branch_offset(L));
   }
   void beqzalc(Register rt, int16_t offset);
-  void beqzalc(Register rt, Label* L) {
-    beqzalc(rt, branch_offset_compact(L, false)>>2);
+  inline void beqzalc(Register rt, Label* L) {
+    beqzalc(rt, shifted_branch_offset(L));
   }
   void beqc(Register rs, Register rt, int16_t offset);
-  void beqc(Register rs, Register rt, Label* L) {
-    beqc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void beqc(Register rs, Register rt, Label* L) {
+    beqc(rs, rt, shifted_branch_offset(L));
   }
   void beqzc(Register rs, int32_t offset);
-  void beqzc(Register rs, Label* L) {
-    beqzc(rs, branch_offset21_compact(L, false)>>2);
+  inline void beqzc(Register rs, Label* L) {
+    beqzc(rs, shifted_branch_offset21(L));
   }
   void bnezalc(Register rt, int16_t offset);
-  void bnezalc(Register rt, Label* L) {
-    bnezalc(rt, branch_offset_compact(L, false)>>2);
+  inline void bnezalc(Register rt, Label* L) {
+    bnezalc(rt, shifted_branch_offset(L));
   }
   void bnec(Register rs, Register rt, int16_t offset);
-  void bnec(Register rs, Register rt, Label* L) {
-    bnec(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bnec(Register rs, Register rt, Label* L) {
+    bnec(rs, rt, shifted_branch_offset(L));
   }
   void bnezc(Register rt, int32_t offset);
-  void bnezc(Register rt, Label* L) {
-    bnezc(rt, branch_offset21_compact(L, false)>>2);
+  inline void bnezc(Register rt, Label* L) {
+    bnezc(rt, shifted_branch_offset21(L));
   }
   void bne(Register rs, Register rt, int16_t offset);
-  void bne(Register rs, Register rt, Label* L) {
-    bne(rs, rt, branch_offset(L, false)>>2);
+  inline void bne(Register rs, Register rt, Label* L) {
+    bne(rs, rt, shifted_branch_offset(L));
   }
   void bovc(Register rs, Register rt, int16_t offset);
-  void bovc(Register rs, Register rt, Label* L) {
-    bovc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bovc(Register rs, Register rt, Label* L) {
+    bovc(rs, rt, shifted_branch_offset(L));
   }
   void bnvc(Register rs, Register rt, int16_t offset);
-  void bnvc(Register rs, Register rt, Label* L) {
-    bnvc(rs, rt, branch_offset_compact(L, false)>>2);
+  inline void bnvc(Register rs, Register rt, Label* L) {
+    bnvc(rs, rt, shifted_branch_offset(L));
   }
 
   // Never use the int16_t b(l)cond version with a branch offset
   // instead of using the Label* version.
 
   // Jump targets must be in the current 256 MB-aligned region. i.e. 28 bits.
   void j(int64_t target);
   void jal(int64_t target);
   void j(Label* target);
   void jal(Label* target);
@@ skipping 274 matching lines @@
   void cvt_d_l(FPURegister fd, FPURegister fs);
   void cvt_d_s(FPURegister fd, FPURegister fs);
 
   // Conditions and branches for MIPSr6.
   void cmp(FPUCondition cond, SecondaryField fmt,
          FPURegister fd, FPURegister ft, FPURegister fs);
   void cmp_s(FPUCondition cond, FPURegister fd, FPURegister fs, FPURegister ft);
   void cmp_d(FPUCondition cond, FPURegister fd, FPURegister fs, FPURegister ft);
 
   void bc1eqz(int16_t offset, FPURegister ft);
-  void bc1eqz(Label* L, FPURegister ft) {
-    bc1eqz(branch_offset(L, false)>>2, ft);
+  inline void bc1eqz(Label* L, FPURegister ft) {
+    bc1eqz(shifted_branch_offset(L), ft);
   }
   void bc1nez(int16_t offset, FPURegister ft);
-  void bc1nez(Label* L, FPURegister ft) {
-    bc1nez(branch_offset(L, false)>>2, ft);
+  inline void bc1nez(Label* L, FPURegister ft) {
+    bc1nez(shifted_branch_offset(L), ft);
   }
 
   // Conditions and branches for non MIPSr6.
   void c(FPUCondition cond, SecondaryField fmt,
          FPURegister ft, FPURegister fs, uint16_t cc = 0);
   void c_s(FPUCondition cond, FPURegister ft, FPURegister fs, uint16_t cc = 0);
   void c_d(FPUCondition cond, FPURegister ft, FPURegister fs, uint16_t cc = 0);
 
   void bc1f(int16_t offset, uint16_t cc = 0);
-  void bc1f(Label* L, uint16_t cc = 0) {
-    bc1f(branch_offset(L, false)>>2, cc);
+  inline void bc1f(Label* L, uint16_t cc = 0) {
+    bc1f(shifted_branch_offset(L), cc);
   }
   void bc1t(int16_t offset, uint16_t cc = 0);
-  void bc1t(Label* L, uint16_t cc = 0) {
-    bc1t(branch_offset(L, false)>>2, cc);
+  inline void bc1t(Label* L, uint16_t cc = 0) {
+    bc1t(shifted_branch_offset(L), cc);
   }
   void fcmp(FPURegister src1, const double src2, FPUCondition cond);
 
   // Check the code size generated from label to here.
   int SizeOfCodeGeneratedSince(Label* label) {
     return pc_offset() - label->pos();
   }
 
   // Check the number of instructions generated from label to here.
   int InstructionsGeneratedSince(Label* label) {
@@ skipping 100 matching lines @@
   static void instr_at_put(byte* pc, Instr instr) {
     *reinterpret_cast<Instr*>(pc) = instr;
   }
   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 IsBc(Instr instr);
+  static bool IsBzc(Instr instr);
+
   static bool IsBeq(Instr instr);
   static bool IsBne(Instr instr);
+  static bool IsBeqzc(Instr instr);
+  static bool IsBnezc(Instr instr);
+  static bool IsBeqc(Instr instr);
+  static bool IsBnec(Instr instr);
+
 
   static bool IsJump(Instr instr);
   static bool IsJ(Instr instr);
   static bool IsLui(Instr instr);
   static bool IsOri(Instr instr);
 
   static bool IsJal(Instr instr);
   static bool IsJr(Instr instr);
   static bool IsJalr(Instr instr);
 
@@ skipping 38 matching lines @@
 
   void CheckTrampolinePool();
 
   void PatchConstantPoolAccessInstruction(int pc_offset, int offset,
                                           ConstantPoolEntry::Access access,
                                           ConstantPoolEntry::Type type) {
     // No embedded constant pool support.
     UNREACHABLE();
   }
 
+  bool IsPrevInstrCompactBranch() { return prev_instr_compact_branch_; }
+
  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.
   TypeFeedbackId recorded_ast_id_;
 
   inline static void set_target_internal_reference_encoded_at(Address pc,
                                                               Address target);
 
   int64_t buffer_space() const { return reloc_info_writer.pos() - pc_; }
@@ skipping 46 matching lines @@
 
   void EndBlockGrowBuffer() {
     DCHECK(block_buffer_growth_);
     block_buffer_growth_ = false;
   }
 
   bool is_buffer_growth_blocked() const {
     return block_buffer_growth_;
   }
 
+  void EmitPendingInstructions() {

[balazs.kilvady, 2015/12/18 19:18:05]

Nice solution. Should be backported to 32-bit. Although I think a better
function name could be used. This function emits only a branch-safe nop if
needed not any "pending" instruction. What about EmitCompactBranchInstruction()
to match to other functions from this function group?

[ivica.bogosavljevic, 2015/12/22 10:22:39]

I was thinking the same thing as you did, to use the name
EmitCompactBranchForbiddenSlotInstruction, but the reason why i though this name
a bit better is basically with this change we introduce some kind of delayed
assembly. Delayed assembly allows us to wait until a sequence of instructions is
generated and do some optimizations on it. So if it is ok, I would like to keep
this name

[balazs.kilvady, 2015/12/22 11:01:56]

I don't agree. Actually Assembler class is for direct MIPS assembly instructions
and MacroAssembler is for adding some 'tricks' to the assembler. Actually this
forbidden-slot-guard is breaking the rule which is not nice. But we should not
add any more delay tricks to Assembler class IMO. So we should not use this
function for any other purposes and we should not add a generic name to it.

[ivica.bogosavljevic, 2015/12/22 12:23:41]

Acknowledged.

+    if (IsPrevInstrCompactBranch()) {
+      nop();
+      ClearCompactBranchState();
+    }
+  }
+
+  inline void CheckTrampolinePoolQuick(int extra_instructions = 0);
+
  private:
   // 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.
@@ skipping 19 matching lines @@
   bool block_buffer_growth_;  // Block growth when true.
 
   // 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_;
 
+  // Readable constants for compact branch handling in emit()
+  enum class CompactBranchType : bool { NO = false, COMPACT_BRANCH = true };
+
   // Code emission.
   inline void CheckBuffer();
   void GrowBuffer();
-  inline void emit(Instr x);
-  inline void emit(uint64_t x);
-  inline void CheckTrampolinePoolQuick(int extra_instructions = 0);
+  inline void emit(Instr x,
+                   CompactBranchType is_compact_branch = CompactBranchType::NO);
+  inline void emit(uint64_t x,
+                   CompactBranchType is_compact_branch = CompactBranchType::NO);
 

[balazs.kilvady, 2015/12/18 19:18:05]

A 64-bit value cannot be a real instruction so it cannot be a compact branch, I
think. If it is true then please remove the 2nd parameter of this
emit(uint64_t).

[ivica.bogosavljevic, 2015/12/22 10:22:39]

Acknowledged.

   // 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.
 
   void GenInstrRegister(Opcode opcode,
                         Register rs,
@@ skipping 30 matching lines @@
                         FPURegister fd,
                         SecondaryField func = NULLSF);
 
   void GenInstrRegister(Opcode opcode,
                         SecondaryField fmt,
                         Register rt,
                         FPUControlRegister fs,
                         SecondaryField func = NULLSF);
 
 
-  void GenInstrImmediate(Opcode opcode,
-                         Register rs,
-                         Register rt,
-                         int32_t  j);
-  void GenInstrImmediate(Opcode opcode,
-                         Register rs,
-                         SecondaryField SF,
-                         int32_t  j);
-  void GenInstrImmediate(Opcode opcode,
-                         Register r1,
-                         FPURegister r2,
-                         int32_t  j);
-  void GenInstrImmediate(Opcode opcode, Register rs, int32_t j);
-  void GenInstrImmediate(Opcode opcode, int32_t offset26);
-
+  void GenInstrImmediate(
+      Opcode opcode, Register rs, Register rt, int32_t j,
+      CompactBranchType is_compact_branch = CompactBranchType::NO);
+  void GenInstrImmediate(
+      Opcode opcode, Register rs, SecondaryField SF, int32_t j,
+      CompactBranchType is_compact_branch = CompactBranchType::NO);
+  void GenInstrImmediate(
+      Opcode opcode, Register r1, FPURegister r2, int32_t j,
+      CompactBranchType is_compact_branch = CompactBranchType::NO);
+  void GenInstrImmediate(
+      Opcode opcode, Register rs, int32_t offset21,
+      CompactBranchType is_compact_branch = CompactBranchType::NO);
+  void GenInstrImmediate(Opcode opcode, Register rs, uint32_t offset21);
+  void GenInstrImmediate(
+      Opcode opcode, int32_t offset26,
+      CompactBranchType is_compact_branch = CompactBranchType::NO);
 
   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);
@@ skipping 53 matching lines @@
   int32_t get_trampoline_entry(int32_t pos);
   int unbound_labels_count_;
   // After trampoline is emitted, long branches are used in generated code for
   // the forward branches whose target offsets could be beyond reach of branch
   // instruction. We use this information to trigger different mode of
   // branch instruction generation, where we use jump instructions rather
   // than regular branch instructions.
   bool trampoline_emitted_;
   static const int kTrampolineSlotsSize = 2 * kInstrSize;
   static const int kMaxBranchOffset = (1 << (18 - 1)) - 1;
+  static const int kMaxCompactBranchOffset = (1 << (28 - 1)) - 1;
   static const int kInvalidSlotPos = -1;
 
   // Internal reference positions, required for unbounded internal reference
   // labels.
   std::set<int64_t> internal_reference_positions_;
 
+  void EmittedCompactBranchInstruction() { prev_instr_compact_branch_ = true; }
+  void ClearCompactBranchState() { prev_instr_compact_branch_ = false; }
+  bool prev_instr_compact_branch_ = false;
+
   Trampoline trampoline_;
   bool internal_trampoline_exception_;
 
   friend class RegExpMacroAssemblerMIPS;
   friend class RelocInfo;
   friend class CodePatcher;
   friend class BlockTrampolinePoolScope;
 
   PositionsRecorder positions_recorder_;
   friend class PositionsRecorder;
   friend class EnsureSpace;
 };
 
 
 class EnsureSpace BASE_EMBEDDED {
  public:
   explicit EnsureSpace(Assembler* assembler) {
     assembler->CheckBuffer();
   }
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_ARM_ASSEMBLER_MIPS_H_