[mips] Teach the delay slot filler to remove needless KILL instructions.

[vkalintiris]

Summary

Previously, the presence of KILL instructions would block valid candidates
from filling a specific delay slot. With the elimination of the KILL
instructions, in the appropriate range, we are able to fill more slots and
keep the information from future def/use analysis consistent.

[hfinkel]

Why are you removing them instead of just ignoring them? Are they really useless, or are they marking subregister/superregister points of definition?

[vkalintiris]

Hi Hal,

In D7724#125595, @hfinkel wrote:

Why are you removing them instead of just ignoring them?

Can we simply ignore them and under what conditions?
I sent an email to the llvm-dev list the other day but it didn't receive much attention:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/081716.html

Are they really useless, or are they marking subregister/superregister points of definition?

I'm not very sure what you are asking me here. AFAIK, the Mips target
doesn't use KILL instructions for anything special. The question is
whether they are used for anything else outside the Mips target.

[hfinkel]

In D7724#125702, @vkalintiris wrote:

Hi Hal,

In D7724#125595, @hfinkel wrote:

Why are you removing them instead of just ignoring them?

Can we simply ignore them and under what conditions?
I sent an email to the llvm-dev list the other day but it didn't receive much attention:

I apologize for the delay in responding.

http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/081716.html

Are they really useless, or are they marking subregister/superregister points of definition?

I'm not very sure what you are asking me here. AFAIK, the Mips target
doesn't use KILL instructions for anything special. The question is
whether they are used for anything else outside the Mips target.

I re-read the llvmdev thread, and I think the conclusion there is correct: Given that you're calling TRI.invalidateLiveness(), removing the KILL instructions makes sense. They're used by the RA, copy propagation, post-RA-scheduler's anti-dependency breakers, etc., but otherwise, they likely don't really matter. So, as Quentin said, removing them is fine.

[vkalintiris]

I re-read the llvmdev thread, and I think the conclusion there is correct: Given that you're calling TRI.invalidateLiveness(), removing the KILL instructions makes sense. They're used by the RA, copy propagation, post-RA-scheduler's anti-dependency breakers, etc., but otherwise, they likely don't really matter. So, as Quentin said, removing them is fine.

Hi Hal, thank you for your comments. I'm glad that the changes are okay!

[dsanders]

Sorry, I didn't realize you were waiting for me.

LGTM

lib/Target/Mips/MipsDelaySlotFiller.cpp

 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
   return new Filler(tm);
 }
 
 template<typename IterTy>
 bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
                          RegDefsUses &RegDU, InspectMemInstr& IM,
                          IterTy &Filler, Iter Slot) const {
-  for (IterTy I = Begin; I != End; ++I) {
+  bool IsReverseIter = std::is_convertible<IterTy, ReverseIter>::value;
+
+  for (IterTy I = Begin; I != End;) {
+    IterTy CurrI = I;
+    ++I;
+
     // skip debug value
-    if (I->isDebugValue())
+    if (CurrI->isDebugValue())
       continue;
 
-    if (terminateSearch(*I))
+    if (terminateSearch(*CurrI))
       break;
 
-    assert((!I->isCall() && !I->isReturn() && !I->isBranch()) &&
+    assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
            "Cannot put calls, returns or branches in delay slot.");
 
-    if (delayHasHazard(*I, RegDU, IM))
+    if (CurrI->isKill()) {
+      CurrI->eraseFromParent();
+
+      // This special case is needed for reverse iterators, because when we
+      // erase an instruction, the iterators are updated to point to the next
+      // instruction.
+      if (IsReverseIter && I != End)
+        I = CurrI;
+      continue;
+    }
+
+    if (delayHasHazard(*CurrI, RegDU, IM))
       continue;
 
     const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
     if (STI.isTargetNaCl()) {
       // In NaCl, instructions that must be masked are forbidden in delay slots.
       // We only check for loads, stores and SP changes.  Calls, returns and
       // branches are not checked because non-NaCl targets never put them in
       // delay slots.
       unsigned AddrIdx;
-      if ((isBasePlusOffsetMemoryAccess(I->getOpcode(), &AddrIdx) &&
-           baseRegNeedsLoadStoreMask(I->getOperand(AddrIdx).getReg())) ||
-          I->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
+      if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
+           baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) ||
+          CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
         continue;
     }
 
     bool InMicroMipsMode = STI.inMicroMipsMode();
     const MipsInstrInfo *TII = STI.getInstrInfo();
     unsigned Opcode = (*Slot).getOpcode();
-    if (InMicroMipsMode && TII->GetInstSizeInBytes(&(*I)) == 2 &&
+    if (InMicroMipsMode && TII->GetInstSizeInBytes(&(*CurrI)) == 2 &&
         (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
          Opcode == Mips::PseudoReturn))
       continue;
 
-    Filler = I;
+    Filler = CurrI;
     return true;
   }
 
   return false;
 }
 
 bool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const {
   if (DisableBackwardSearch)
bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
   }
 
   BrMap[&Pred] = P.second;
   return true;
 }
 
 bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
                             InspectMemInstr &IM) const {
-  bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill());
+  assert(!Candidate.isKill() &&
+         "KILL instructions should have been eliminated at this point.");
+
+  bool HasHazard = Candidate.isImplicitDef();
 
   HasHazard |= IM.hasHazard(Candidate);
   HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
 
   return HasHazard;
 }
 
 bool Filler::terminateSearch(const MachineInstr &Candidate) const {
   return (Candidate.isTerminator() || Candidate.isCall() ||
           Candidate.isPosition() || Candidate.isInlineAsm() ||
           Candidate.hasUnmodeledSideEffects());
 }

test/CodeGen/Mips/delay-slot-kill.ll

+; RUN: llc < %s -march=mips64 -mcpu=mips3 | FileCheck %s
+
+; Currently, the following IR assembly generates a KILL instruction between
+; the bitwise-and instruction and the return instruction. We verify that the
+; delay slot filler ignores such KILL instructions by filling the slot of the
+; return instruction properly.
+define signext i32 @f1(i32 signext %a, i32 signext %b) {
+entry:
+  ; CHECK:          jr      $ra
+  ; CHECK-NEXT:     and     $2, $4, $5
+
+  %r = and i32 %a, %b
+  ret i32 %r
+}