[RDA] Track implicit-defs

[samparker]

Summary

Ensure that we're recording implicit defs, as well as visiting implicit uses and implicit defs when we're walking through operands. This requires a change to ARMLowOverheadLoops because RDA now knows that t2LoopEnd is set to define the CPSR.

[samparker]

Rebased for new test case.

[SjoerdMeijer]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

129

I am thinking if it is time for a MO helper function that tests this, because I see a lot of the same/similar checks:

if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
if (!MO.isReg() || MO.isUndef() || !MO.getReg())
if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
if (!MO.isReg() || MO.isUse() || MO.getReg() == 0)
if (!MO.isReg() || MO.getReg() == 0 || !MO.isKill())
if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)

Perhaps a local static helper function(s) is easiest to increase readability?

[samparker]

Adding a few helpers for use/defs.

[SjoerdMeijer]

Thanks for that! That greatly helps readability!

Where in this patch stack do we expect test changes?

[samparker]

Rebased after reverting to show the test changes that we want.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

820

Do we need to start looking again for t2LoopEnd? Is that not saved to End, do we have access to that?

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

820

We still need this because t2LoopEnd isn't actually the last instruction, there's almost certainly an unconditional branch as the terminator, so this code was originally not doing what is was supposed to! Now that we're correctly tracking implicit-defs, RDA will pick up that !isSafeToDefRegAt because t2LoopEnd has an implicit CPSR def and we definitely want to ignore it.

[SjoerdMeijer]

Thanks, LGTM

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "reaching-deps-analysis"
 
 char ReachingDefAnalysis::ID = 0;
 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
                 true)
 
+bool isValidReg(const MachineOperand &MO) {
+  return MO.isReg() && MO.getReg();
+}
+
+bool isValidRegUse(const MachineOperand &MO) {
+  return isValidReg(MO) && MO.isUse();
+}
+
+bool isValidRegUseOf(const MachineOperand &MO, int PhysReg) {
+  return isValidRegUse(MO) && MO.getReg() == PhysReg;
+}
+
+bool isKilledRegUse(const MachineOperand &MO) {
+  return isValidRegUse(MO) && MO.isKill();
+}
+
+bool isValidRegDef(const MachineOperand &MO) {
+  return isValidReg(MO) && MO.isDef();
+}
+
+bool isValidRegDefOf(const MachineOperand &MO, int PhysReg) {
+  return isValidRegDef(MO) && MO.getReg() == PhysReg;
+}
+
 void ReachingDefAnalysis::enterBasicBlock(
     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 
   MachineBasicBlock *MBB = TraversedMBB.MBB;
   unsigned MBBNumber = MBB->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&
          "Unexpected basic block number.");
   MBBReachingDefs[MBBNumber].resize(NumRegUnits);

 }
 
 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
   assert(!MI->isDebugInstr() && "Won't process debug instructions");
 
   unsigned MBBNumber = MI->getParent()->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&
          "Unexpected basic block number.");
-  const MCInstrDesc &MCID = MI->getDesc();
-  for (unsigned i = 0,
-                e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
-       i != e; ++i) {
-    MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || !MO.getReg())
-      continue;
-    if (MO.isUse())
+
+  for (auto &MO : MI->operands()) {
+    if (!isValidRegDef(MO))
       continue;
     for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
       // This instruction explicitly defines the current reg unit.
       LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
                         << '\t' << *MI);
 
       // How many instructions since this reg unit was last written?
       LiveRegs[*Unit] = CurInstr;
if (MI->isDebugInstr())
       continue;
 
     // If/when we find a new reaching def, we know that there's no more uses
     // of 'Def'.
     if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
       return;
 
     for (auto &MO : MI->operands()) {
-      if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
+      if (!isValidRegUseOf(MO, PhysReg))
         continue;
 
       Uses.insert(&*MI);
       if (MO.isKill())
         return;
     }
   }
 }
 
 bool
 ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
                                    InstSet &Uses) const {
   for (auto &MI : *MBB) {
     if (MI.isDebugInstr())
       continue;
     for (auto &MO : MI.operands()) {
-      if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
+      if (!isValidRegUseOf(MO, PhysReg))
         continue;
       if (getReachingDef(&MI, PhysReg) >= 0)
         return false;
       Uses.insert(&MI);
     }
   }
   return isReachingDefLiveOut(&MBB->back(), PhysReg);
 }
ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
 
   MachineInstr *Last = &MBB->back();
   int Def = getReachingDef(MI, PhysReg);
   if (getReachingDef(Last, PhysReg) != Def)
     return false;
 
   // Finally check that the last instruction doesn't redefine the register.
   for (auto &MO : Last->operands())
-    if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
+    if (isValidRegDefOf(MO, PhysReg))
       return false;
 
   return true;
 }
 
 MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
                                                         int PhysReg) const {
   LivePhysRegs LiveRegs(*TRI);
   LiveRegs.addLiveOuts(*MBB);
   if (!LiveRegs.contains(PhysReg))
     return nullptr;
 
   MachineInstr *Last = &MBB->back();
   int Def = getReachingDef(Last, PhysReg);
   for (auto &MO : Last->operands())
-    if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
+    if (isValidRegDefOf(MO, PhysReg))
       return Last;
 
   return Def < 0 ? nullptr : getInstFromId(MBB, Def);
 }
 
 static bool mayHaveSideEffects(MachineInstr &MI) {
   return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
          MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
          MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
 }
 
 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
 // not define a register that is used by any instructions, after and including,
 // 'To'. These instructions also must not redefine any of Froms operands.
 template<typename Iterator>
 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
                                        MachineInstr *To) const {
   if (From->getParent() != To->getParent())
     return false;
 
   SmallSet<int, 2> Defs;
   // First check that From would compute the same value if moved.
   for (auto &MO : From->operands()) {
-    if (!MO.isReg() || MO.isUndef() || !MO.getReg())
+    if (!isValidReg(MO))
       continue;
     if (MO.isDef())
       Defs.insert(MO.getReg());
     else if (!hasSameReachingDef(From, To, MO.getReg()))
       return false;
   }
 
   // Now walk checking that the rest of the instructions will compute the same
ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
   else if (mayHaveSideEffects(*MI)) {
     // Unless told to ignore the instruction, don't remove anything which has
     // side effects.
     return false;
   }
 
   Visited.insert(MI);
   for (auto &MO : MI->operands()) {
-    if (!MO.isReg() || MO.isUse() || MO.getReg() == 0)
+    if (!isValidRegDef(MO))
       continue;
 
     SmallPtrSet<MachineInstr*, 4> Uses;
     getGlobalUses(MI, MO.getReg(), Uses);
 
     for (auto I : Uses) {
       if (Ignore.count(I) || ToRemove.count(I))
         continue;
       if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
         return false;
     }
   }
   ToRemove.insert(MI);
   return true;
 }
 
 void ReachingDefAnalysis::collectLocalKilledOperands(MachineInstr *MI,
                                                      InstSet &Dead) const {
   Dead.insert(MI);
   auto IsDead = [this](MachineInstr *Def, int PhysReg) {
     unsigned LiveDefs = 0;
-    for (auto &MO : Def->defs())
+    for (auto &MO : Def->operands()) {
+      if (!isValidRegDef(MO))
+        continue;
       if (!MO.isDead())
         ++LiveDefs;
+    }
 
     if (LiveDefs > 1)
       return false;
 
     SmallPtrSet<MachineInstr*, 4> Uses;
     getGlobalUses(Def, PhysReg, Uses);
     return Uses.size() == 1;
   };
 
-  for (auto &MO : MI->uses()) {
-    if (!MO.isReg() || MO.getReg() == 0 || !MO.isKill())
+  for (auto &MO : MI->operands()) {
+    if (!isKilledRegUse(MO))
       continue;
     if (MachineInstr *Def = getReachingLocalMIDef(MI, MO.getReg()))
       if (IsDead(Def, MO.getReg()))
         collectLocalKilledOperands(Def, Dead);
   }
 }
 
 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, int PhysReg,
   MachineBasicBlock *MBB = MI->getParent();
   // Check for any defs after MI.
   if (isRegDefinedAfter(MI, PhysReg)) {
     auto I = MachineBasicBlock::iterator(MI);
     for (auto E = MBB->end(); I != E; ++I) {
       if (Ignore.count(&*I))
         continue;
       for (auto &MO : I->operands())
-        if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
+        if (isValidRegDefOf(MO, PhysReg))
           return false;
     }
   }
   return true;
 }

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
   MIB.addImm(ARMCC::EQ);        // condition code
   MIB.addReg(ARM::CPSR);
   MI->eraseFromParent();
 }
 
 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
   LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
   MachineBasicBlock *MBB = MI->getParent();
-  MachineInstr *Last = &MBB->back();
   SmallPtrSet<MachineInstr*, 1> Ignore;
-  if (Last->getOpcode() == ARM::t2LoopEnd)
-    Ignore.insert(Last);
+  for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
+    if (I->getOpcode() == ARM::t2LoopEnd) {
+      Ignore.insert(&*I);
+      break;
+    }
+  }
 
   // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
   bool SetFlags = RDA->isSafeToDefRegAt(MI, ARM::CPSR, Ignore);
 
   MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                     TII->get(ARM::t2SUBri));
   MIB.addDef(ARM::LR);
   MIB.add(MI->getOperand(1));

llvm/test/CodeGen/Thumb2/LowOverheadLoops/cmplx_cong.mir

stack:
   - { id: 1, name: '', type: spill-slot, offset: -8, size: 4, alignment: 4,
       stack-id: default, callee-saved-register: '$r4', callee-saved-restored: true,
       debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
 machineFunctionInfo: {}
 body:             |
   ; CHECK-LABEL: name: arm_cmplx_conj_f32_mve
   ; CHECK: bb.0:
   ; CHECK:   successors: %bb.1(0x80000000)
-  ; CHECK:   liveins: $lr, $r0, $r1, $r3, $r4
+  ; CHECK:   liveins: $lr, $r0, $r1, $r2, $r4
   ; CHECK:   frame-setup tPUSH 14 /* CC::al */, $noreg, killed $r4, killed $lr, implicit-def $sp, implicit $sp
   ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 8
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r4, -8
-  ; CHECK:   tCMPi8 renamable $r3, 4, 14 /* CC::al */, $noreg, implicit-def dead $cpsr
-  ; FIXME:   tLSRi needs to be producing the value in r3
+  ; CHECK:   renamable $r3, dead $cpsr = tLSLri killed renamable $r2, 1, 14 /* CC::al */, $noreg
   ; CHECK:   $r4 = t2MOVi16 target-flags(arm-lo16) @arm_cmplx_conj_f32_mve.cmplx_conj_sign, 14 /* CC::al */, $noreg
   ; CHECK:   $r4 = t2MOVTi16 killed $r4, target-flags(arm-hi16) @arm_cmplx_conj_f32_mve.cmplx_conj_sign, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $q0 = nnan ninf nsz MVE_VLDRWU32 killed renamable $r4, 0, 0, $noreg
   ; CHECK:   $lr = MVE_DLSTP_32 killed renamable $r3
   ; CHECK: bb.1 (align 4):
   ; CHECK:   successors: %bb.1(0x7c000000), %bb.2(0x04000000)
   ; CHECK:   liveins: $lr, $q0, $r0, $r1
   ; CHECK:   renamable $q1 = nnan ninf nsz MVE_VLDRWU32 renamable $r0, 0, 0, $noreg

llvm/test/CodeGen/Thumb2/LowOverheadLoops/dont-ignore-vctp.mir

- id:              0
     value:           '<4 x float> <float 1.000000e+00, float -1.000000e+00, float 1.000000e+00, float -1.000000e+00>'
     alignment:       16
     isTargetSpecific: false
 machineFunctionInfo: {}
 body:             |
   ; CHECK-LABEL: name: dont_ignore_vctp
   ; CHECK: bb.0.entry:
   ; CHECK:   successors: %bb.1(0x80000000)
-  ; CHECK:   liveins: $lr, $r0, $r1, $r3, $r7
+  ; CHECK:   liveins: $lr, $r0, $r1, $r2, $r7
   ; CHECK:   frame-setup tPUSH 14 /* CC::al */, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
   ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 8
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r7, -8
-  ; CHECK:   tCMPi8 renamable $r3, 4, 14 /* CC::al */, $noreg, implicit-def dead $cpsr
+  ; CHECK:   renamable $r3, dead $cpsr = tLSLri killed renamable $r2, 1, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r2 = tLEApcrel %const.0, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $q0 = MVE_VLDRWU32 killed renamable $r2, 0, 0, $noreg :: (load 16 from constant-pool)
   ; CHECK:   $lr = MVE_DLSTP_32 killed renamable $r3
   ; CHECK: bb.1.do.body (align 4):
   ; CHECK:   successors: %bb.1(0x7c000000), %bb.2(0x04000000)
   ; CHECK:   liveins: $lr, $q0, $r0, $r1
   ; CHECK:   renamable $q1 = nnan ninf nsz MVE_VLDRWU32 renamable $r0, 0, 0, $noreg
   ; CHECK:   renamable $q1 = nnan ninf nsz MVE_VMULf32 killed renamable $q1, renamable $q0, 0, $noreg, undef renamable $q1