[RDA][ARM] collectKilledOperands across multiple blocks

[samparker]

Summary

Use MIOperand in collectLocalKilledOperands to make the search global, as we already have to search for global uses too. This allows us to delete more dead code when tail predicating.

[samparker]

Rebased and changed the way we collect the IT blocks.

[samparker]

• Fixed a bug in getUniqueReachingMIDef.
• During operand collection, visit all uses and not just killed ones.

[SjoerdMeijer]

Nice optimisation, looks very reasonable to me: LGTM

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

public:
   /// Return whether From can be moved forwards to just before To.
   bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const;
 
   /// Return whether From can be moved backwards to just after To.
   bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const;
 
   /// Assuming MI is dead, recursively search the incoming operands which are
   /// killed by MI and collect those that would become dead.
-  void collectLocalKilledOperands(MachineInstr *MI, InstSet &Dead) const;
+  void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const;
 
   /// Return whether removing this instruction will have no effect on the
   /// program, returning the redundant use-def chain.
   bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const;
 
   /// Return whether removing this instruction will have no effect on the
   /// program, ignoring the possible effects on some instructions, returning
   /// the redundant use-def chain.

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

 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;
 }
 
else
     for (auto *Pred : MBB->predecessors())
       getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
 }
 
 MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
                                                           int PhysReg) const {
   // If there's a local def before MI, return it.
   MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
-  if (InstIds.lookup(LocalDef) < InstIds.lookup(MI))
+  if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
     return LocalDef;
 
   SmallPtrSet<MachineBasicBlock*, 4> VisitedBBs;
   SmallPtrSet<MachineInstr*, 2> Incoming;
   for (auto *Pred : MI->getParent()->predecessors())
     getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs);
 
   // If we have a local def and an incoming instruction, then there's not a
for (auto I : Uses) {
       if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
         return false;
     }
   }
   ToRemove.insert(MI);
   return true;
 }
 
-void ReachingDefAnalysis::collectLocalKilledOperands(MachineInstr *MI,
-                                                     InstSet &Dead) const {
+void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
   Dead.insert(MI);
   auto IsDead = [this, &Dead](MachineInstr *Def, int PhysReg) {
     unsigned LiveDefs = 0;
     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);
     for (auto *Use : Uses)
       if (!Dead.count(Use))
         return false;
     return true;
   };
 
   for (auto &MO : MI->operands()) {
-    if (!isKilledRegUse(MO))
+    if (!isValidRegUse(MO))
       continue;
-    if (MachineInstr *Def = getReachingLocalMIDef(MI, MO.getReg()))
+    if (MachineInstr *Def = getMIOperand(MI, MO))
       if (IsDead(Def, MO.getReg()))
-        collectLocalKilledOperands(Def, Dead);
+        collectKilledOperands(Def, Dead);
   }
 }
 
 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
                                            int PhysReg) const {
   SmallPtrSet<MachineInstr*, 1> Ignore;
   return isSafeToDefRegAt(MI, PhysReg, Ignore);
 }

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

 // Thus, $r3 which defines the number of elements, is written to $lr,
 // and then we want to delete the whole chain that used to define $lr,
 // see the comment below how this chain could look like.
 //
 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
   if (!LoLoop.IsTailPredicationLegal())
     return;
 
+  LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
+
   MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 0);
-  if (!Def)
+  if (!Def) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
     return;
+  }
 
-  // Collect IT blocks.
+  // Collect and remove the users of iteration count.
+  SmallPtrSet<MachineInstr*, 4> Killed  = { LoLoop.Start, LoLoop.Dec,
+                                            LoLoop.End, LoLoop.InsertPt };
+  SmallPtrSet<MachineInstr*, 2> Remove;
+  if (RDA->isSafeToRemove(Def, Remove, Killed))
+    LoLoop.ToRemove.insert(Remove.begin(), Remove.end());
+  else {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
+    return;
+  }
+
+  // Collect the dead code and the MBBs in which they reside.
+  RDA->collectKilledOperands(Def, Killed);
+  SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
+  for (auto *MI : Killed)
+    BasicBlocks.insert(MI->getParent());
+
+  // Collect IT blocks in all affected basic blocks.
   std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
-  std::map<MachineInstr *, MachineInstr *> Predicates;
-  MachineInstr *IT = nullptr;
-  for (auto &MI : *Def->getParent()) {
-    if (MI.getOpcode() == ARM::t2IT)
-      IT = &MI;
-    else if (TII->getPredicate(MI) != ARMCC::AL) {
-      ITBlocks[IT].insert(&MI);
-      Predicates[&MI] = IT;
+  for (auto *MBB : BasicBlocks) {
+    for (auto &MI : *MBB) {
+      if (MI.getOpcode() != ARM::t2IT)
+        continue;
+      RDA->getReachingLocalUses(&MI, ARM::ITSTATE, ITBlocks[&MI]);
     }
   }
 
   // If we're removing all of the instructions within an IT block, then
   // also remove the IT instruction.
   SmallPtrSet<MachineInstr*, 2> ModifiedITs;
-  SmallPtrSet<MachineInstr*, 2> DeadITs;
-  SmallPtrSet<MachineInstr*, 4> Killed;
-  RDA->collectLocalKilledOperands(Def, Killed);
   for (auto *MI : Killed) {
-    if (!Predicates.count(MI))
-      continue;
-
-    MachineInstr *IT = Predicates[MI];
+    if (MachineOperand *MO = MI->findRegisterUseOperand(ARM::ITSTATE)) {
+      MachineInstr *IT = RDA->getMIOperand(MI, *MO);
       auto &CurrentBlock = ITBlocks[IT];
       CurrentBlock.erase(MI);
-    ModifiedITs.insert(IT);
-    if (CurrentBlock.empty()) {
-      DeadITs.insert(IT);
+      if (CurrentBlock.empty())
         ModifiedITs.erase(IT);
+      else
+        ModifiedITs.insert(IT);
     }
   }
 
   // Delete the killed instructions only if we don't have any IT blocks that
   // need to be modified because we need to fixup the mask.
   // TODO: Handle cases where IT blocks are modified.
   if (ModifiedITs.empty()) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Will remove iteration count:\n";
                for (auto *MI : Killed)
                  dbgs() << " - " << *MI);
     LoLoop.ToRemove.insert(Killed.begin(), Killed.end());
-  }
-
-  // Collect and remove the users of iteration count.
-  SmallPtrSet<MachineInstr*, 4> Ignore = { LoLoop.Start, LoLoop.Dec,
-                                           LoLoop.End, LoLoop.InsertPt };
-  SmallPtrSet<MachineInstr*, 2> Remove;
-  if (RDA->isSafeToRemove(Def, Remove, Ignore))
-    LoLoop.ToRemove.insert(Remove.begin(), Remove.end());
+  } else
+    LLVM_DEBUG(dbgs() << "ARM Loops: Would need to modify IT block(s).\n");
 }
 
 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
   LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
   // When using tail-predication, try to delete the dead code that was used to
   // calculate the number of loop iterations.
   IterationCountDCE(LoLoop);
 
auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
     unsigned Opc = LoLoop.IsTailPredicationLegal() ?
       ARM::MVE_LETP : ARM::t2LEUpdate;
     MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
                                       TII->get(Opc));
     MIB.addDef(ARM::LR);
     MIB.add(End->getOperand(0));
     MIB.add(End->getOperand(1));
     LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
-    LoLoop.Dec->eraseFromParent();
-    End->eraseFromParent();
+    LoLoop.ToRemove.insert(LoLoop.Dec);
+    LoLoop.ToRemove.insert(End);
     return &*MIB;
   };
 
   // TODO: We should be able to automatically remove these branches before we
   // get here - probably by teaching analyzeBranch about the pseudo
   // instructions.
   // If there is an unconditional branch, after I, that just branches to the
   // next block, remove it.

llvm/test/CodeGen/Thumb2/LowOverheadLoops/it-block-itercount.mir

body:             |
   ; CHECK: bb.0.entry:
   ; CHECK:   successors: %bb.1(0x80000000)
   ; 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:   renamable $r3, dead $cpsr = tLSLri killed renamable $r2, 1, 14 /* CC::al */, $noreg
-  ; CHECK:   dead renamable $r12 = t2MOVi 4, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   tCMPi8 renamable $r3, 4, 14 /* CC::al */, $noreg, implicit-def dead $cpsr
   ; 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

llvm/test/CodeGen/Thumb2/LowOverheadLoops/it-block-mov.mir

body:             |
   ; CHECK-LABEL: name: cond_trip_count
   ; CHECK: bb.0:
   ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
   ; 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 $r1, 4, 14 /* CC::al */, $noreg, implicit-def $cpsr
-  ; CHECK:   renamable $r3 = t2MOVi 4, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   t2IT 11, 8, implicit-def $itstate
-  ; CHECK:   dead $r3 = tMOVr renamable $r1, 11 /* CC::lt */, killed $cpsr, implicit killed renamable $r3, implicit killed $itstate
   ; CHECK:   tCMPi8 renamable $r1, 2, 14 /* CC::al */, $noreg, implicit-def $cpsr
-  ; CHECK:   renamable $r12 = t2MOVi 4, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   tBcc %bb.2, 2 /* CC::hs */, killed $cpsr
   ; CHECK: bb.1:
   ; CHECK:   liveins: $r2
   ; CHECK:   renamable $s0 = VLDRS %const.0, 0, 14 /* CC::al */, $noreg
   ; CHECK:   VSTRS killed renamable $s0, killed renamable $r2, 0, 14 /* CC::al */, $noreg
   ; CHECK:   tPOP_RET 14 /* CC::al */, $noreg, def $r4, def $pc
   ; CHECK: bb.2:
   ; CHECK:   successors: %bb.3(0x80000000)
-  ; CHECK:   liveins: $r0, $r1, $r2, $r12
-  ; CHECK:   renamable $r4, dead $cpsr = tMOVi8 1, 14 /* CC::al */, $noreg
-  ; CHECK:   tCMPi8 renamable $r1, 4, 14 /* CC::al */, $noreg, implicit-def $cpsr
-  ; CHECK:   t2IT 11, 8, implicit-def $itstate
-  ; CHECK:   $r12 = tMOVr renamable $r1, 11 /* CC::lt */, killed $cpsr, implicit killed renamable $r12, implicit killed $itstate
-  ; CHECK:   renamable $r3 = t2SUBrr renamable $r1, killed renamable $r12, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   renamable $r3, dead $cpsr = tADDi8 killed renamable $r3, 3, 14 /* CC::al */, $noreg
+  ; CHECK:   liveins: $r0, $r1, $r2
   ; CHECK:   $r12 = tMOVr $r1, 14 /* CC::al */, $noreg
-  ; CHECK:   dead renamable $r4 = nuw nsw t2ADDrs killed renamable $r4, killed renamable $r3, 19, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
   ; CHECK:   $r3 = tMOVr $r0, 14 /* CC::al */, $noreg
   ; CHECK:   $lr = MVE_DLSTP_32 killed renamable $r12
   ; CHECK: bb.3:
   ; CHECK:   successors: %bb.3(0x7c000000), %bb.4(0x04000000)
   ; CHECK:   liveins: $lr, $q0, $r0, $r1, $r2, $r3
   ; CHECK:   renamable $q1 = nnan ninf nsz MVE_VLDRWU32 renamable $r3, 0, 0, $noreg
   ; CHECK:   renamable $q0 = nnan ninf nsz MVE_VADDf32 killed renamable $q0, killed renamable $q1, 0, killed $noreg, killed renamable $q0

llvm/test/CodeGen/Thumb2/LowOverheadLoops/multiple-do-loops.mir

body:             |
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r6, -12
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r5, -16
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r4, -20
   ; CHECK:   dead $r7 = frame-setup tADDrSPi $sp, 3, 14 /* CC::al */, $noreg
   ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa $r7, 8
   ; CHECK:   early-clobber $sp = frame-setup t2STR_PRE killed $r8, $sp, -4, 14 /* CC::al */, $noreg
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r8, -24
   ; CHECK:   renamable $r6, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
-  ; CHECK:   dead renamable $r12 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   t2CMPrs killed renamable $r6, renamable $r3, 11, 14 /* CC::al */, $noreg, implicit-def $cpsr
   ; CHECK:   tBcc %bb.3, 0 /* CC::eq */, killed $cpsr
   ; CHECK: bb.1.vector.ph:
   ; CHECK:   successors: %bb.2(0x80000000)
   ; CHECK:   liveins: $r0, $r1, $r2, $r3
   ; CHECK:   renamable $r4, dead $cpsr = tLSRri renamable $r3, 1, 14 /* CC::al */, $noreg
   ; CHECK:   $r8 = tMOVr $r0, 14 /* CC::al */, $noreg
   ; CHECK:   $r5 = tMOVr $r1, 14 /* CC::al */, $noreg
body:             |
   ; CHECK:   renamable $r5, renamable $q1 = MVE_VLDRWU32_post killed renamable $r5, 16, 0, $noreg :: (load 16 from %ir.lsr.iv120122, align 4)
   ; CHECK:   renamable $q0 = nsw MVE_VMULi32 killed renamable $q1, killed renamable $q0, 0, $noreg, undef renamable $q0
   ; CHECK:   renamable $r8 = MVE_VSTRWU32_post killed renamable $q0, killed renamable $r8, 16, 0, killed $noreg :: (store 16 into %ir.lsr.iv123125, align 4)
   ; CHECK:   $lr = MVE_LETP killed renamable $lr, %bb.2
   ; CHECK: bb.3.for.cond4.preheader:
   ; CHECK:   successors: %bb.6(0x30000000), %bb.4(0x50000000)
   ; CHECK:   liveins: $r0, $r1, $r2, $r3
   ; CHECK:   renamable $r6, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
-  ; CHECK:   dead renamable $r8 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   t2CMPrs killed renamable $r6, renamable $r3, 11, 14 /* CC::al */, $noreg, implicit-def $cpsr
   ; CHECK:   tBcc %bb.6, 0 /* CC::eq */, killed $cpsr
   ; CHECK: bb.4.vector.ph66:
   ; CHECK:   successors: %bb.5(0x80000000)
   ; CHECK:   liveins: $r0, $r1, $r2, $r3
   ; CHECK:   renamable $r5, dead $cpsr = tLSRri renamable $r3, 1, 14 /* CC::al */, $noreg
   ; CHECK:   $r10 = tMOVr $r0, 14 /* CC::al */, $noreg
   ; CHECK:   $r9 = tMOVr $r2, 14 /* CC::al */, $noreg

llvm/test/CodeGen/Thumb2/mve-postinc-lsr.ll

 
 
 ; Similar but predicated
 define i32 @arm_nn_mat_mul_core_4x_s8(i32 %row_elements, i32 %offset, i8* %row_base, i8* %col_base, i32* nocapture readnone %sum_col, i32* nocapture %output) {
 ; CHECK-LABEL: arm_nn_mat_mul_core_4x_s8:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r4, r5, r6, r7, r8, r10, lr}
 ; CHECK-NEXT:    push.w {r4, r5, r6, r7, r8, r10, lr}
-; CHECK-NEXT:    add.w r7, r0, #15
 ; CHECK-NEXT:    ldr.w r12, [sp, #32]
-; CHECK-NEXT:    mov.w lr, #1
-; CHECK-NEXT:    asrs r6, r7, #31
-; CHECK-NEXT:    add.w r4, r7, r6, lsr #28
-; CHECK-NEXT:    asrs r5, r4, #4
-; CHECK-NEXT:    cmp r5, #1
-; CHECK-NEXT:    it gt
-; CHECK-NEXT:    asrgt.w lr, r4, #4
 ; CHECK-NEXT:    cmp r0, #1
 ; CHECK-NEXT:    blt .LBB4_3
 ; CHECK-NEXT:  @ %bb.1: @ %for.body.preheader
 ; CHECK-NEXT:    adds r5, r2, r1
 ; CHECK-NEXT:    add.w r7, r2, r1, lsl #1
 ; CHECK-NEXT:    add.w r1, r1, r1, lsl #1
 ; CHECK-NEXT:    mov.w r8, #0
 ; CHECK-NEXT:    add r1, r2