Modify MIPS long branch for NaCl

[sstankovic]

Summary

[mips] Modify long branch for NaCl:

• Move the instruction that changes sp outside of the branch delay slot.
• Bundle-align the target of indirect branch.

[mseaborn]

LGTM

BTW, if you're hitting this when targeting NaCl at the moment, you should probably turn off PIC code generation, since you don't need PIC for NaCl nexes.

lib/Target/Mips/MipsLongBranch.cpp

474

Could the code grow by more than a factor of 2? Some explanation of the max expansion factor here would be good.

e.g. "lw $sp, ($reg)" requires 2 sandboxing instructions to be added (before and after).

[sstankovic]

BTW, if you're hitting this when targeting NaCl at the moment, you should probably turn off PIC code generation, since you don't need PIC for NaCl nexes.

Should this be done in LLVM, or in pnacl/driver scripts?

lib/Target/Mips/MipsLongBranch.cpp

474

We measured code size on CSiBE, for pic relocation model (which on MIPS produces larger code than static), and sandboxing increased the size in the range 28% - 48%. I think it is very unlikely that the code will grow more than 100%.

[sstankovic]

MIPS traditionally used PIC relocation model, to be able to use shared libraries. PLT support (which enables non-PIC code to use shared libraries) was added to MIPS only recently, in 2008. I suppose at that time GCC switched to using non-PIC as default. I don't know why LLVM still uses PIC.

Regards,
Sasa

[sstankovic]

Committed in r210262.

lib/Target/Mips/MipsLongBranch.cpp

 // This pass expands a branch or jump instruction into a long branch if its
 // offset is too large to fit into its immediate field.
 //
 // FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
 //===----------------------------------------------------------------------===//
 
 #include "Mips.h"
 #include "MCTargetDesc/MipsBaseInfo.h"
+#include "MCTargetDesc/MipsMCNaCl.h"
 #include "MipsTargetMachine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetInstrInfo.h"
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 ? 10 : 9)) {}
+        LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 10 :
+            (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl() ? 9 : 10))) {}
 
     const char *getPassName() const override {
       return "Mips Long Branch";
     }
 
     bool runOnMachineFunction(MachineFunction &F) override;
 
   private:
if (ABI != MipsSubtarget::N64) {
 
       Pos = BalTgtMBB->begin();
 
       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
         .addReg(Mips::RA).addReg(Mips::AT);
       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
         .addReg(Mips::SP).addImm(0);
 
+      if (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) {
         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 {
+        // In NaCl, modifying the sp is not allowed in branch delay slot.
+        BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
+          .addReg(Mips::SP).addImm(8);
+
+        MIBundleBuilder(*BalTgtMBB, Pos)
+          .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT))
+          .append(BuildMI(*MF, DL, TII->get(Mips::NOP)));
+
+        // Bundle-align the target of indirect branch JR.
+        TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
+      }
+    } else {
       // $longbr:
       //  daddiu $sp, $sp, -16
       //  sd $ra, 0($sp)
       //  daddiu $at, $zero, %hi($tgt - $baltgt)
       //  dsll $at, $at, 16
       //  bal $baltgt
       //  daddiu $at, $at, %lo($tgt - $baltgt)
       // $baltgt:
while (MadeChange) {
 
     for (I = MBBInfos.begin(); I != E; ++I) {
       // Skip if this MBB doesn't have a branch or the branch has already been
       // converted to a long branch.
       if (!I->Br || I->HasLongBranch)
         continue;
 
       int ShVal = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode() ? 2 : 4;
+      int64_t Offset = computeOffset(I->Br) / ShVal;
+
+      if (TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) {
+        // The offset calculation does not include sandboxing instructions
+        // that will be added later in the MC layer.  Since at this point we
+        // don't know the exact amount of code that "sandboxing" will add, we
+        // conservatively estimate that code will not grow more than 100%.
+        Offset *= 2;
+      }
 
       // Check if offset fits into 16-bit immediate field of branches.
-      if (!ForceLongBranch && isInt<16>(computeOffset(I->Br) / ShVal))
+      if (!ForceLongBranch && isInt<16>(Offset))
         continue;
 
       I->HasLongBranch = true;
       I->Size += LongBranchSeqSize * 4;
       ++LongBranches;
       EverMadeChange = MadeChange = true;
     }
   }

test/CodeGen/Mips/longbranch.ll

 ; RUN: llc -march=mipsel < %s | FileCheck %s
 ; RUN: llc -march=mipsel -force-mips-long-branch -O3 < %s \
 ; RUN:   | FileCheck %s -check-prefix=O32
 ; RUN: llc -march=mips64el -mcpu=mips4 -mattr=n64 -force-mips-long-branch -O3 \
 ; RUN:   < %s | FileCheck %s -check-prefix=N64
 ; RUN: llc -march=mips64el -mcpu=mips64 -mattr=n64 -force-mips-long-branch -O3 \
 ; RUN:   < %s | FileCheck %s -check-prefix=N64
 ; RUN: llc -march=mipsel -mcpu=mips32r2 -mattr=micromips \
 ; RUN:   -force-mips-long-branch -O3 < %s | FileCheck %s -check-prefix=MICROMIPS
+; RUN: llc -mtriple=mipsel-none-nacl -force-mips-long-branch -O3 < %s \
+; RUN:   | FileCheck %s -check-prefix=NACL
 
 
 @x = external global i32
 
 define void @test1(i32 %s) {
 entry:
   %cmp = icmp eq i32 %s, 0
   br i1 %cmp, label %end, label %then

 
 ; MICROMIPS:   $[[BB0]]:
 ; MICROMIPS:        lw      $[[R1:[0-9]+]], %got(x)($[[GP]])
 ; MICROMIPS:        addiu   $[[R2:[0-9]+]], $zero, 1
 ; MICROMIPS:        sw      $[[R2]], 0($[[R1]])
 ; MICROMIPS:   $[[BB2]]:
 ; MICROMIPS:        jr      $ra
 ; MICROMIPS:        nop
+
+
+; Check the NaCl version.  Check that sp change is not in the branch delay slot
+; of "jr $1" instruction.  Check that target of indirect branch "jr $1" is
+; bundle aligned.
+
+; NACL:        lui     $[[R0:[0-9]+]], %hi(_gp_disp)
+; NACL:        addiu   $[[R0]], $[[R0]], %lo(_gp_disp)
+; NACL:        bnez    $4, $[[BB0:BB[0-9_]+]]
+; NACL:        addu    $[[GP:[0-9]+]], $[[R0]], $25
+
+; Check for long branch expansion:
+; NACL:             addiu   $sp, $sp, -8
+; NACL-NEXT:        sw      $ra, 0($sp)
+; NACL-NEXT:        lui     $1, %hi(($[[BB2:BB[0-9_]+]])-($[[BB1:BB[0-9_]+]]))
+; NACL-NEXT:        bal     $[[BB1]]
+; NACL-NEXT:        addiu   $1, $1, %lo(($[[BB2]])-($[[BB1]]))
+; NACL-NEXT:   $[[BB1]]:
+; NACL-NEXT:        addu    $1, $ra, $1
+; NACL-NEXT:        lw      $ra, 0($sp)
+; NACL-NEXT:        addiu   $sp, $sp, 8
+; NACL-NEXT:        jr      $1
+; NACL-NEXT:        nop
+
+; NACL:        $[[BB0]]:
+; NACL:             lw      $[[R1:[0-9]+]], %got(x)($[[GP]])
+; NACL:             addiu   $[[R2:[0-9]+]], $zero, 1
+; NACL:             sw      $[[R2]], 0($[[R1]])
+; NACL:             .align  4
+; NACL-NEXT:   $[[BB2]]:
+; NACL:             jr      $ra
+; NACL:             nop
 }