Optimize long branch for MIPS64 by removing calculation of %higher and %highest

[sstankovic]

Summary

[mips] Optimize long branch for MIPS64 by removing %higher and %highest. %higher and %highest can have non-zero values only for offsets greater than 4GB, which is highly unlikely, if not impossible when compiling a single function. This makes long branch for MIPS64 3 instructions smaller.

[mseaborn]

lib/Target/Mips/MipsLongBranch.cpp

327

Does 64-bit MIPS not have an instruction for setting bits 16-31 of a register while zeroing the others (as 32-bit MIPS' "lui" instruction does)?

What does lui64 do?

This part looks OK to me, but I'm not familiar with 64-bit MIPS, so you might want to get someone who is sign off on the change too.

352–353

Is this change based on your not-yet-committed change? If you, presumably you should remove LONG_BRANCH_LUi64 too? Or you might want to commit this change first so that you don't have to add LONG_BRANCH_LUi64?

[sstankovic]

Patch is updated.

[dsanders]

lib/Target/Mips/MipsLongBranch.cpp

327

Does 64-bit MIPS not have an instruction for setting bits 16-31 of a register while
zeroing the others (as 32-bit MIPS' "lui" instruction does)?

Not while zeroing the other bits but 32-bit results are generally sign-extended to 64-bit. lui is nearly the right operation but sign-extends instead of zero extending.

What does lui64 do?

lui64 doesn't exist in the assembler or the ISA spec so we ought to avoid using that term when writing assembly examples. It's the same as the 32-bit lui instruction but sign-extended to 64-bits.

---

It looks like you should be able to remove another insn by replacing:

daddiu $at, $zero, 0
daddiu $at, $at, %hi($tgt - $baltgt)

with:

daddiu $at, $zero, %hi($tgt - $baltgt)

349–363

This logic makes sense to me but I didn't notice a guarantee that $tgt and $baltgt are in the same function. Have I missed it?

[mseaborn]

@Sasa: You have confused me a bit by having interdependent changes in flight at the same time, which is why I've been slow coming back to this.

When you post an updated patch in reply to a review, could you possibly reply to each of the review comments, even if it's just to say "Done"?

I wrote "Is this change based on your not-yet-committed change? If so, presumably you should remove LONG_BRANCH_LUi64 too?". Since the current version of the patch does remove LONG_BRANCH_LUi64, it looks like the answer to my first question was "yes", but it would be better if you answered directly, so that I don't have to deduce it from the change to the patch.

[sstankovic]

@Sasa: You have confused me a bit by having interdependent changes in flight at the same time, which is why
I've been slow coming back to this.

When you post an updated patch in reply to a review, could you possibly reply to each of the review comments,
even if it's just to say "Done"?

I wrote "Is this change based on your not-yet-committed change? If so, presumably you should remove
LONG_BRANCH_LUi64 too?". Since the current version of the patch does remove LONG_BRANCH_LUi64,
it looks like the answer to my first question was "yes", but it would be better if you answered directly, so that
I don't have to deduce it from the change to the patch.

Actually I did answered, but I don't know why the answers were not visible; maybe because I sent them together with the updated patch, and they were related to the code that was removed. The answers were only visible in the link that shows the change since the last diff. To your question:

Is this change based on your not-yet-committed change? If you, presumably you should remove LONG_BRANCH_LUi64 too? Or you might want to commit this change first so that you don't have to add LONG_BRANCH_LUi64?

I answered:

I removed LONG_BRANCH_LUi64.

And to your question:

What does lui64 do?

I answered:

There is no lui64 (I fixed that comment), there is only a lui instruction (you can see it in .td file lib/Target/Mips/Mips64InstrInfo.td - mnemonic for MIPS64 LUi64 instruction is just "lui"). lui on MIPS64 sets bits 16-31 of a register, zeroes bits 15-0, and sign-extends bit 31 into higher part of the 64-bit register. MIPS64 supports all (or almost all) MIPS32 instructions, and they all operate like this - they change low 32 bits just like they do on MIPS32, and they sign-extend bit 31 into high 32 bits. MIPS64 also has instructions that operate on all 64 bits (their mnemonics start with d (from double)), but there is no instruction that sets bits 16-31 while clearing the others.

I suppose that I should not send inline comments together with the updated patch, but rather before or after I send the patch.

lib/Target/Mips/MipsLongBranch.cpp

327

There is no lui64 (I fixed that comment), there is only a lui instruction (you can see it in .td file lib/Target/Mips/Mips64InstrInfo.td - mnemonic for MIPS64 LUi64 instruction is just "lui"). lui on MIPS64 sets bits 16-31 of a register, zeroes bits 15-0, and sign-extends bit 31 into higher part of the 64-bit register. MIPS64 supports all (or almost all) MIPS32 instructions, and they all operate like this - they change low 32 bits just like they do on MIPS32, and they sign-extend bit 31 into high 32 bits. MIPS64 also has instructions that operate on all 64 bits (their mnemonics start with d (from double)), but there is no instruction that sets bits 16-31 while clearing the others.

352–353

I removed LONG_BRANCH_LUi64.

[sstankovic]

lib/Target/Mips/MipsLongBranch.cpp

327

You are right, I'll implement this.

349–363

Do you want that I add the assert that that $tgt and $baltgt are in the current function? $baltgt is always in the current function because it is part of the long branch. As for $tgt, it is the target operand of the original branch that is expanded into long branch. I suppose that branches always jump to the blocks in the same function, but I may be wrong.

[sstankovic]

Additionally optimize long branch for MIPS64 by removing one more instruction.

[sstankovic]

Updated the patch to reflect changes to patch D3089.

[sstankovic]

@Mark: Are there any new comments on this patch?

[mseaborn]

LGTM for the code change, with the caveat about tail calls below and the warning that I'm not an expert on MIPS. :-)

lib/Target/Mips/MipsLongBranch.cpp

345

Including this snippet seems a bit too verbose to me. You don't need to document what the code used to do -- we have version control for that. :-)

Just say you assume the jump is within-function, so the offset is within +/- 2GB.

352

I don't think you answered dsanders' question about why it's valid to assume that the jump is within-function.

I was wondering whether tail calls to other functions would become jumps that would need handling via MipsLongBranch. The answer seems to be that LLVM always compiles function calls to indirect jumps on MIPS. (However, GCC does compile tail calls to direct jumps.) That answer seems a bit crazy, so I'm not sure if it's right. You should check. Does the MIPS linker insert veneers to handle long direct jumps the same way ARM linkers do?

[sstankovic]

I modified the comment.

[sstankovic]

lib/Target/Mips/MipsLongBranch.cpp

345

Done

352

I don't think you answered dsanders' question about why it's valid to assume that the
jump is within-function.

I didn't answer because I wasn't aware of the cases where jumps are outside of a function. I just suggested that we can add assert that the branch target is within function.

I was wondering whether tail calls to other functions would become jumps that would > need handling via MipsLongBranch. The answer seems to be that LLVM always
compiles function calls to indirect jumps on MIPS. (However, GCC does compile tail > calls to direct jumps.) That answer seems a bit crazy, so I'm not sure if it's right. You > should check. Does the MIPS linker insert veneers to handle long direct jumps the
same way ARM linkers do?

I checked tail calls on LLVM and GCC, and they generate similar code when given explicit relocation model on the command line. When relocation model is omitted the code differs because default for MIPS GCC is non-pic, and for MIPS LLVM is pic. For pic code (which this patch handles) tail calls are replaced by load from GOT and indirect jump:

lw $t9, %call16(func)($gp)
jr $t9

and this doesn't need long branch.

As for veneers, MIPS GNU ld linker doesn't insert them.

[sstankovic]

Committed in r209678.

lib/Target/Mips/Mips64InstrInfo.td

let isCodeGenOnly = 1, rs = 0, shamt = 0 in {
   def DSLL64_32 : FR<0x00, 0x3c, (outs GPR64:$rd), (ins GPR32:$rt),
                      "dsll\t$rd, $rt, 32", [], II_DSLL>;
   def SLL64_32 : FR<0x0, 0x00, (outs GPR64:$rd), (ins GPR32:$rt),
                     "sll\t$rd, $rt, 0", [], II_SLL>;
   def SLL64_64 : FR<0x0, 0x00, (outs GPR64:$rd), (ins GPR64:$rt),
                     "sll\t$rd, $rt, 0", [], II_SLL>;
 }
 
-// We need the following two pseudo instructions to avoid offset calculation for
+// We need the following pseudo instruction to avoid offset calculation for
 // long branches.  See the comment in file MipsLongBranch.cpp for detailed
 // explanation.
 
-// Expands to: lui $dst, %highest($tgt - $baltgt)
-def LONG_BRANCH_LUi64 : PseudoSE<(outs GPR64Opnd:$dst),
-  (ins brtarget:$tgt, brtarget:$baltgt), []>;
-
 // Expands to: daddiu $dst, $src, %PART($tgt - $baltgt)
-// where %PART may be %higher, %hi or %lo, depending on the relocation kind
+// where %PART may be %hi or %lo, depending on the relocation kind
 // that $tgt is annotated with.
 def LONG_BRANCH_DADDiu : PseudoSE<(outs GPR64Opnd:$dst),
   (ins GPR64Opnd:$src, brtarget:$tgt, brtarget:$baltgt), []>;
 
 // Cavium Octeon cmMIPS instructions
 let Predicates = [HasCnMips] in {
 
 class Count1s<string opstr, RegisterOperand RO>:

lib/Target/Mips/MipsAsmPrinter.cpp

for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
     if (MBB->hasAddressTaken())
       MBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
   }
 }
 
 bool MipsAsmPrinter::isLongBranchPseudo(int Opcode) const {
   return (Opcode == Mips::LONG_BRANCH_LUi
           || Opcode == Mips::LONG_BRANCH_ADDiu
-          || Opcode == Mips::LONG_BRANCH_LUi64
           || Opcode == Mips::LONG_BRANCH_DADDiu);
 }
 
 // Force static initialization.
 extern "C" void LLVMInitializeMipsAsmPrinter() {
   RegisterAsmPrinter<MipsAsmPrinter> X(TheMipsTarget);
   RegisterAsmPrinter<MipsAsmPrinter> Y(TheMipselTarget);
   RegisterAsmPrinter<MipsAsmPrinter> A(TheMips64Target);
   RegisterAsmPrinter<MipsAsmPrinter> B(TheMips64elTarget);
 }

lib/Target/Mips/MipsLongBranch.cpp

namespace {
   class MipsLongBranch : public MachineFunctionPass {
 
   public:
     static char ID;
     MipsLongBranch(TargetMachine &tm)
       : MachineFunctionPass(ID), TM(tm),
         IsPIC(TM.getRelocationModel() == Reloc::PIC_),
         ABI(TM.getSubtarget<MipsSubtarget>().getTargetABI()),
-        LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 13 : 9)) {}
+        LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 10 : 9)) {}
 
     virtual const char *getPassName() const {
       return "Mips Long Branch";
     }
 
     bool runOnMachineFunction(MachineFunction &F);
 
   private:
if (ABI != MipsSubtarget::N64) {
       MIBundleBuilder(*BalTgtMBB, Pos)
         .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT))
         .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP)
                 .addReg(Mips::SP).addImm(8));
     } else {
       // $longbr:
       //  daddiu $sp, $sp, -16
       //  sd $ra, 0($sp)
-      //  lui64 $at, %highest($tgt - $baltgt)
-      //  daddiu $at, $at, %higher($tgt - $baltgt)
-      //  dsll $at, $at, 16
-      //  daddiu $at, $at, %hi($tgt - $baltgt)
+      //  daddiu $at, $zero, %hi($tgt - $baltgt)
       //  dsll $at, $at, 16
       //  bal $baltgt
       //  daddiu $at, $at, %lo($tgt - $baltgt)
       // $baltgt:
       //  daddu $at, $ra, $at
       //  ld $ra, 0($sp)
       //  jr64 $at
       //  daddiu $sp, $sp, 16
       // $fallthrough:
       //
 
-      // TODO: %highest and %higher can have non-zero values only when the
-      // offset is greater than 4GB, which is highly unlikely.  Replace
-      // them (and the following instructon that shifts $at by 16) with the
-      // instruction that sets $at to zero.
+      // Note that we optimized offset calculation by using
+      //
+      //   daddiu $at, $zero, %hi($tgt - $baltgt)
+      //
+      // instead of
+      //
+      //   lui $at, %highest($tgt - $baltgt)
+      //   daddiu $at, $at, %higher($tgt - $baltgt)
+      //   dsll $at, $at, 16
+      //   daddiu $at, $at, %hi($tgt - $baltgt)
+      //
+      // It's safe to do this because %highest and %higher can have non-zero
+      // values only when the offset is greater than 4GB, which is highly
+      // unlikely, if not impossible when compiling a single function.
+      //
+      // Note that this will work even if the offset is negative, because
+      // of the +1 modification that's added in that case.  For example, if the
+      // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
+      //
+      // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
+      //
+      // and the bits [47:32] are zero.  For %highest
+      //
+      // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
+      //
+      // and the bits [63:48] are zero.
 
       Pos = LongBrMBB->begin();
 
       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
         .addReg(Mips::SP_64).addImm(-16);
       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64)
         .addReg(Mips::SP_64).addImm(0);
-      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi64),
-              Mips::AT_64).addMBB(TgtMBB).addMBB(BalTgtMBB);
-      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
-              Mips::AT_64).addReg(Mips::AT_64).addMBB(TgtMBB, MipsII::MO_HIGHER)
-                          .addMBB(BalTgtMBB);
-      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
-        .addReg(Mips::AT_64).addImm(16);
       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
-              Mips::AT_64).addReg(Mips::AT_64).addMBB(TgtMBB, MipsII::MO_ABS_HI)
-                          .addMBB(BalTgtMBB);
+              Mips::AT_64).addReg(Mips::ZERO_64)
+                          .addMBB(TgtMBB, MipsII::MO_ABS_HI).addMBB(BalTgtMBB);
       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
         .addReg(Mips::AT_64).addImm(16);
 
       MIBundleBuilder(*LongBrMBB, Pos)
         .append(BuildMI(*MF, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB))
         .append(BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
                         Mips::AT_64).addReg(Mips::AT_64)
                                     .addMBB(TgtMBB, MipsII::MO_ABS_LO)

lib/Target/Mips/MipsMCInstLower.h

public:
   void Lower(const MachineInstr *MI, MCInst &OutMI) const;
   MCOperand LowerOperand(const MachineOperand& MO, unsigned offset = 0) const;
 
 private:
   MCOperand LowerSymbolOperand(const MachineOperand &MO,
                                MachineOperandType MOTy, unsigned Offset) const;
   MCOperand createSub(MachineBasicBlock *BB1, MachineBasicBlock *BB2,
                       MCSymbolRefExpr::VariantKind Kind) const;
-  void lowerLongBranchLUi(const MachineInstr *MI, MCInst &OutMI,
-                          int Opcode, MCSymbolRefExpr::VariantKind Kind) const;
+  void lowerLongBranchLUi(const MachineInstr *MI, MCInst &OutMI) const;
   void lowerLongBranchADDiu(const MachineInstr *MI, MCInst &OutMI,
                             int Opcode,
                             MCSymbolRefExpr::VariantKind Kind) const;
   bool lowerLongBranch(const MachineInstr *MI, MCInst &OutMI) const;
 };
 }
 
 #endif

lib/Target/Mips/MipsMCInstLower.cpp

MCOperand MipsMCInstLower::createSub(MachineBasicBlock *BB1,
   const MCSymbolRefExpr *Sym1 = MCSymbolRefExpr::Create(BB1->getSymbol(), *Ctx);
   const MCSymbolRefExpr *Sym2 = MCSymbolRefExpr::Create(BB2->getSymbol(), *Ctx);
   const MCBinaryExpr *Sub = MCBinaryExpr::CreateSub(Sym1, Sym2, *Ctx);
 
   return MCOperand::CreateExpr(MipsMCExpr::Create(Kind, Sub, *Ctx));
 }
 
 void MipsMCInstLower::
-lowerLongBranchLUi(const MachineInstr *MI, MCInst &OutMI, int Opcode,
-                   MCSymbolRefExpr::VariantKind Kind) const {
-  OutMI.setOpcode(Opcode);
+lowerLongBranchLUi(const MachineInstr *MI, MCInst &OutMI) const {
+  OutMI.setOpcode(Mips::LUi);
 
   // Lower register operand.
   OutMI.addOperand(LowerOperand(MI->getOperand(0)));
 
-  // Create %hi($tgt-$baltgt) or %highest($tgt-$baltgt).
+  // Create %hi($tgt-$baltgt).
   OutMI.addOperand(createSub(MI->getOperand(1).getMBB(),
-                             MI->getOperand(2).getMBB(), Kind));
+                             MI->getOperand(2).getMBB(),
+                             MCSymbolRefExpr::VK_Mips_ABS_HI));
 }
 
 void MipsMCInstLower::
 lowerLongBranchADDiu(const MachineInstr *MI, MCInst &OutMI, int Opcode,
                      MCSymbolRefExpr::VariantKind Kind) const {
   OutMI.setOpcode(Opcode);
 
   // Lower two register operands.
   for (unsigned I = 0, E = 2; I != E; ++I) {
     const MachineOperand &MO = MI->getOperand(I);
     OutMI.addOperand(LowerOperand(MO));
   }
 
-  // Create %lo($tgt-$baltgt), %hi($tgt-$baltgt) or %higher($tgt-$baltgt).
+  // Create %lo($tgt-$baltgt) or %hi($tgt-$baltgt).
   OutMI.addOperand(createSub(MI->getOperand(2).getMBB(),
                              MI->getOperand(3).getMBB(), Kind));
 }
 
 bool MipsMCInstLower::lowerLongBranch(const MachineInstr *MI,
                                       MCInst &OutMI) const {
   switch (MI->getOpcode()) {
   default:
     return false;
   case Mips::LONG_BRANCH_LUi:
-    lowerLongBranchLUi(MI, OutMI, Mips::LUi, MCSymbolRefExpr::VK_Mips_ABS_HI);
-    return true;
-  case Mips::LONG_BRANCH_LUi64:
-    lowerLongBranchLUi(MI, OutMI, Mips::LUi64,
-                       MCSymbolRefExpr::VK_Mips_HIGHEST);
+    lowerLongBranchLUi(MI, OutMI);
     return true;
   case Mips::LONG_BRANCH_ADDiu:
     lowerLongBranchADDiu(MI, OutMI, Mips::ADDiu,
                          MCSymbolRefExpr::VK_Mips_ABS_LO);
     return true;
   case Mips::LONG_BRANCH_DADDiu:
     unsigned TargetFlags = MI->getOperand(2).getTargetFlags();
-    if (TargetFlags == MipsII::MO_HIGHER)
-      lowerLongBranchADDiu(MI, OutMI, Mips::DADDiu,
-                           MCSymbolRefExpr::VK_Mips_HIGHER);
-    else if (TargetFlags == MipsII::MO_ABS_HI)
+    if (TargetFlags == MipsII::MO_ABS_HI)
       lowerLongBranchADDiu(MI, OutMI, Mips::DADDiu,
                            MCSymbolRefExpr::VK_Mips_ABS_HI);
     else if (TargetFlags == MipsII::MO_ABS_LO)
       lowerLongBranchADDiu(MI, OutMI, Mips::DADDiu,
                            MCSymbolRefExpr::VK_Mips_ABS_LO);
     else
       report_fatal_error("Unexpected flags for LONG_BRANCH_DADDiu");
     return true;

test/CodeGen/Mips/longbranch.ll

 
 ; N64:        lui     $[[R0:[0-9]+]], %hi(%neg(%gp_rel(test1)))
 ; N64:        bnez    $4, $[[BB0:BB[0-9_]+]]
 ; N64:        daddu   $[[R1:[0-9]+]], $[[R0]], $25
 
 ; Check for long branch expansion:
 ; N64:           daddiu  $sp, $sp, -16
 ; N64-NEXT:      sd      $ra, 0($sp)
-; N64-NEXT:      lui     $1, %highest(($[[BB2:BB[0-9_]+]])-($[[BB1:BB[0-9_]+]]))
-; N64-NEXT:      daddiu  $1, $1, %higher(($[[BB2]])-($[[BB1]]))
-; N64-NEXT:      dsll    $1, $1, 16
-; N64-NEXT:      daddiu  $1, $1, %hi(($[[BB2]])-($[[BB1]]))
+; N64-NEXT:      daddiu  $1, $zero, %hi(($[[BB2:BB[0-9_]+]])-($[[BB1:BB[0-9_]+]]))
 ; N64-NEXT:      dsll    $1, $1, 16
 ; N64-NEXT:      bal     $[[BB1]]
 ; N64-NEXT:      daddiu  $1, $1, %lo(($[[BB2]])-($[[BB1]]))
 ; N64-NEXT:  $[[BB1]]:
 ; N64-NEXT:      daddu   $1, $ra, $1
 ; N64-NEXT:      ld      $ra, 0($sp)
 ; N64-NEXT:      jr      $1
 ; N64-NEXT:      daddiu  $sp, $sp, 16