Delay slot filler: Replace the microMIPS BEQ/BNE with the BEQZC/BNEZC

[jkolek]

Summary

This patch implements functionality in MIPS delay slot filler such as if delay slot filler have to put NOP instruction into the delay slot of microMIPS BEQ or BNE instruction which uses the register $0, then instead of emitting NOP this instruction is replaced by the corresponding microMIPS compact branch instruction, i.e. BEQZC or BNEZC.

[dsanders]

LGTM with micromips-long-branch.ll change explained, and with the Br->hasDelaySlot() change.

lib/Target/Mips/MipsDelaySlotFiller.cpp

535–546 ↗

(On Diff #8966)

You don't have to do it in this patch, but the same trick will be useful for MIPS32r6/MIPS64r6. It would be good to use a try/fallback approach so we don't have to add several if-statements. E.g something like:

if (!replaceWithCompactBranch(...))
    bundle a NOP with the branch

where replaceWithCompactBranch() returns true if it sucessfully used a compact branch.

lib/Target/Mips/MipsLongBranch.cpp

240–241 ↗

(On Diff #8966)

I believe this should be:

if (!Br->hasDelaySlot())
  ...

test/CodeGen/Mips/micromips-long-branch.ll

16423 ↗

(On Diff #8966)

Why did this change when nothing else in the file did? I can't think of a reason the patch would change it.

[jkolek]

Rebased patch:

In the function MipsLongBranch::replaceBranch() the condition:

((unsigned) Br->getOpcode()) != Mips::BEQZC_MM && ((unsigned) Br->getOpcode()) != Mips::BNEZC_MM

is replaced with:

Br->hasDelaySlot()

The file 'test/CodeGen/Mips/micromips-long-branch.ll' has been removed since by commit 207656. MicroMIPS long branch is now tested in the file 'test/CodeGen/Mips/longbranch.ll'. Back then the change of value of ADDIU instruction was due to its role in calculation of long branches. The immediate part of ADDIU was something like %lo(($lab1)-($lab2)), and because BEQZ was between $lab1 and $lab2 after it was replaced by BEQZC (no NOP anymore) the immediate value of ADDIU was changed.

[jkolek]

Closed by commit rL222580 (authored by @jkolek).

llvm/trunk/lib/Target/Mips/MipsDelaySlotFiller.cpp

public:
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<MachineBranchProbabilityInfo>();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
   private:
     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
 
+    Iter replaceWithCompactBranch(MachineBasicBlock &MBB,
+                                  Iter Branch, DebugLoc DL);
+
     /// This function checks if it is valid to move Candidate to the delay slot
     /// and returns true if it isn't. It also updates memory and register
     /// dependence information.
     bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
                         InspectMemInstr &IM) const;
 
     /// This function searches range [Begin, End) for an instruction that can be
     /// moved to the delay slot. Returns true on success.
if (!isIdentifiedObject(V))
       return false;
 
     Objects.push_back(*I);
   }
 
   return true;
 }
 
+// Replace Branch with the compact branch instruction.
+Iter Filler::replaceWithCompactBranch(MachineBasicBlock &MBB,
+                                      Iter Branch, DebugLoc DL) {
+  const MipsInstrInfo *TII= static_cast<const MipsInstrInfo *>(
+    TM.getSubtargetImpl()->getInstrInfo());
+
+  unsigned NewOpcode =
+    (((unsigned) Branch->getOpcode()) == Mips::BEQ) ? Mips::BEQZC_MM
+                                                    : Mips::BNEZC_MM;
+
+  const MCInstrDesc &NewDesc = TII->get(NewOpcode);
+  MachineInstrBuilder MIB = BuildMI(MBB, Branch, DL, NewDesc);
+
+  MIB.addReg(Branch->getOperand(0).getReg());
+  MIB.addMBB(Branch->getOperand(2).getMBB());
+
+  Iter tmpIter = Branch;
+  Branch = std::prev(Branch);
+  MBB.erase(tmpIter);
+
+  return Branch;
+}
+
 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 /// We assume there is only one delay slot per delayed instruction.
 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
   bool Changed = false;
   bool InMicroMipsMode = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode();
 
   for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
     if (!hasUnoccupiedSlot(&*I))
if (!InMicroMipsMode || !I->isCall()) {
           if (searchSuccBBs(MBB, I))
             continue;
         } else if (searchForward(MBB, I)) {
           continue;
         }
       }
     }
 
+    // If instruction is BEQ or BNE with one ZERO register, then instead of
+    // adding NOP replace this instruction with the corresponding compact
+    // branch instruction, i.e. BEQZC or BNEZC.
+    unsigned Opcode = I->getOpcode();
+    if (InMicroMipsMode &&
+        (Opcode == Mips::BEQ || Opcode == Mips::BNE) &&
+        ((unsigned) I->getOperand(1).getReg()) == Mips::ZERO) {
+
+      I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());
+
+    } else {
       // Bundle the NOP to the instruction with the delay slot.
       const MipsInstrInfo *TII = static_cast<const MipsInstrInfo *>(
           TM.getSubtargetImpl()->getInstrInfo());
       BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
       MIBundleBuilder(MBB, I, std::next(I, 2));
     }
+  }
 
   return Changed;
 }
 
 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
 /// slots in Mips MachineFunctions
 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
   return new Filler(tm);

llvm/trunk/lib/Target/Mips/MipsLongBranch.cpp

if (!MO.isReg()) {
       break;
     }
 
     MIB.addReg(MO.getReg());
   }
 
   MIB.addMBB(MBBOpnd);
 
+  if (Br->hasDelaySlot()) {
     // Bundle the instruction in the delay slot to the newly created branch
     // and erase the original branch.
     assert(Br->isBundledWithSucc());
     MachineBasicBlock::instr_iterator II(Br);
     MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
+  }
   Br->eraseFromParent();
 }
 
 // Expand branch instructions to long branches.
 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
   MachineBasicBlock::iterator Pos;
   MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
   DebugLoc DL = I.Br->getDebugLoc();

llvm/trunk/lib/Target/Mips/MipsSEInstrInfo.cpp

unsigned MipsSEInstrInfo::getOppositeBranchOpc(unsigned Opc) const {
   case Mips::BEQ64:  return Mips::BNE64;
   case Mips::BNE64:  return Mips::BEQ64;
   case Mips::BGTZ64: return Mips::BLEZ64;
   case Mips::BGEZ64: return Mips::BLTZ64;
   case Mips::BLTZ64: return Mips::BGEZ64;
   case Mips::BLEZ64: return Mips::BGTZ64;
   case Mips::BC1T:   return Mips::BC1F;
   case Mips::BC1F:   return Mips::BC1T;
+  case Mips::BEQZC_MM: return Mips::BNEZC_MM;
+  case Mips::BNEZC_MM: return Mips::BEQZC_MM;
   }
 }
 
 /// Adjust SP by Amount bytes.
 void MipsSEInstrInfo::adjustStackPtr(unsigned SP, int64_t Amount,
                                      MachineBasicBlock &MBB,
                                      MachineBasicBlock::iterator I) const {
   const MipsSubtarget &STI = Subtarget;

 }
 
 unsigned MipsSEInstrInfo::getAnalyzableBrOpc(unsigned Opc) const {
   return (Opc == Mips::BEQ    || Opc == Mips::BNE    || Opc == Mips::BGTZ   ||
           Opc == Mips::BGEZ   || Opc == Mips::BLTZ   || Opc == Mips::BLEZ   ||
           Opc == Mips::BEQ64  || Opc == Mips::BNE64  || Opc == Mips::BGTZ64 ||
           Opc == Mips::BGEZ64 || Opc == Mips::BLTZ64 || Opc == Mips::BLEZ64 ||
           Opc == Mips::BC1T   || Opc == Mips::BC1F   || Opc == Mips::B      ||
-          Opc == Mips::J) ?
+          Opc == Mips::J || Opc == Mips::BEQZC_MM || Opc == Mips::BNEZC_MM) ?
          Opc : 0;
 }
 
 void MipsSEInstrInfo::expandRetRA(MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator I) const {
   if (Subtarget.isGP64bit())
     BuildMI(MBB, I, I->getDebugLoc(), get(Mips::PseudoReturn64))
         .addReg(Mips::RA_64);

llvm/trunk/test/CodeGen/Mips/micromips-atomic.ll

 ; RUN: llc %s -march=mipsel -mcpu=mips32r2 -mattr=micromips -filetype=asm \
 ; RUN: -relocation-model=pic -o - | FileCheck %s
 
 @x = common global i32 0, align 4
 
 define i32 @AtomicLoadAdd32(i32 %incr) nounwind {
 entry:
   %0 = atomicrmw add i32* @x, i32 %incr monotonic
   ret i32 %0
 
 ; CHECK-LABEL:   AtomicLoadAdd32:
 ; CHECK:   lw      $[[R0:[0-9]+]], %got(x)
 ; CHECK:   $[[BB0:[A-Z_0-9]+]]:
 ; CHECK:   ll      $[[R1:[0-9]+]], 0($[[R0]])
 ; CHECK:   addu    $[[R2:[0-9]+]], $[[R1]], $4
 ; CHECK:   sc      $[[R2]], 0($[[R0]])
-; CHECK:   beqz    $[[R2]], $[[BB0]]
+; CHECK:   beqzc   $[[R2]], $[[BB0]]
 }

llvm/trunk/test/CodeGen/Mips/micromips-compact-branches.ll

+; RUN: llc %s -march=mipsel -mattr=micromips -filetype=asm -O3 \
+; RUN: -disable-mips-delay-filler -relocation-model=pic -o - | FileCheck %s
+
+define void @main() nounwind uwtable {
+entry:
+  %x = alloca i32, align 4
+  %0 = load i32* %x, align 4
+  %cmp = icmp eq i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 10, i32* %x, align 4
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK: bnezc