[ARM][LowOverheadLoops] Start insertion point

[samparker]

Summary

If possible, try not to move the start position earlier than it already is.

[samparker]

Now using TryRemove for both LRDef cases.

[samparker]

Checking result of TryRemove.

[samparker]

Rebased.

[SjoerdMeijer]

llvm/test/CodeGen/Thumb2/LowOverheadLoops/mov-operand.ll

32

Maybe you can help me understanding this a bit better with this example. The DLS has been push down a bit, but I am guessing in this case it doesn't really matter?
Which kind of leads me to my more general question(s): is this an optimisation, or a bug fix, and which test case is the best to look at it?

[samparker]

llvm/test/CodeGen/Thumb2/LowOverheadLoops/mov-operand.ll

32

It doesn't really matter for these examples, this patch is just a precursor for improving the tail predication version (since we really don't want any instructions after LSTP in the preheader).

[SjoerdMeijer]

llvm/test/CodeGen/Thumb2/LowOverheadLoops/mov-operand.ll

32

Ok, cheers, in that case LGTM.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

if (Start->getOpcode() == ARM::t2WhileLoopStart &&
       return false;
     }
     return true;
   };
 
   // Find a suitable position to insert the loop start instruction. It needs to
   // be able to safely define LR.
   auto FindStartInsertionPoint = [](MachineInstr *Start,
+                                    MachineInstr *Dec,
                                     MachineBasicBlock::iterator &InsertPt,
                                     MachineBasicBlock *&InsertBB,
-                                    ReachingDefAnalysis &RDA) {
+                                    ReachingDefAnalysis &RDA,
+                                    InstSet &ToRemove) {
     // We can define LR because LR already contains the same value.
     if (Start->getOperand(0).getReg() == ARM::LR) {
       InsertPt = MachineBasicBlock::iterator(Start);
       InsertBB = Start->getParent();
       return true;
     }
 
     unsigned CountReg = Start->getOperand(0).getReg();
     auto IsMoveLR = [&CountReg](MachineInstr *MI) {
       return MI->getOpcode() == ARM::tMOVr &&
              MI->getOperand(0).getReg() == ARM::LR &&
              MI->getOperand(1).getReg() == CountReg &&
              MI->getOperand(2).getImm() == ARMCC::AL;
     };
 
-    MachineBasicBlock *MBB = Start->getParent();
-
     // Find an insertion point:
     // - Is there a (mov lr, Count) before Start? If so, and nothing else
-    //   writes to Count before Start, we can insert at that mov.
+    //   writes to Count before Start, we can insert at start.
     if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR)) {
       if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg)) {
-        InsertPt = MachineBasicBlock::iterator(LRDef);
-        InsertBB = LRDef->getParent();
+        SmallPtrSet<MachineInstr *, 2> Ignore = { Dec };
+        if (!TryRemove(LRDef, RDA, ToRemove, Ignore))
+          return false;
+        InsertPt = MachineBasicBlock::iterator(Start);
+        InsertBB = Start->getParent();
         return true;
       }
     }
 
     // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
-    //   to Count after Start, we can insert at that mov.
+    //   to Count after Start, we can insert at that mov (which will now be
+    //   dead).
+    MachineBasicBlock *MBB = Start->getParent();
     if (auto *LRDef = RDA.getLocalLiveOutMIDef(MBB, ARM::LR)) {
       if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg)) {
+        SmallPtrSet<MachineInstr *, 2> Ignore = { Start, Dec };
+        if (!TryRemove(LRDef, RDA, ToRemove, Ignore))
+          return false;
         InsertPt = MachineBasicBlock::iterator(LRDef);
         InsertBB = LRDef->getParent();
         return true;
       }
     }
 
     // We've found no suitable LR def and Start doesn't use LR directly. Can we
     // just define LR anyway?
     if (!RDA.isSafeToDefRegAt(Start, ARM::LR))
       return false;
 
     InsertPt = MachineBasicBlock::iterator(Start);
     InsertBB = Start->getParent();
     return true;
   };
 
-  if (!FindStartInsertionPoint(Start, StartInsertPt, StartInsertBB, RDA)) {
+  if (!FindStartInsertionPoint(Start, Dec, StartInsertPt, StartInsertBB, RDA,
+                               ToRemove)) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
     Revert = true;
     return;
   }
   Revert = !ValidateRanges(Start, End, BBUtils, ML);
   CannotTailPredicate = !ValidateTailPredicate();
 }
 
void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
   if (!Def) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
     return;
   }
 
   // Collect and remove the users of iteration count.
   SmallPtrSet<MachineInstr*, 4> Killed  = { LoLoop.Start, LoLoop.Dec,
                                             LoLoop.End };
-  if (LoLoop.StartInsertPt != LoLoop.StartInsertBB->end())
-    Killed.insert(&*LoLoop.StartInsertPt);
-
   if (!TryRemove(Def, *RDA, LoLoop.ToRemove, Killed))
     LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\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.
MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
   MachineInstrBuilder MIB =
     BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));
 
   MIB.addDef(ARM::LR);
   MIB.add(Count);
   if (!IsDo)
     MIB.add(Start->getOperand(1));
 
-  // If we're inserting at a mov lr, then remove it as it's redundant.
-  if (InsertPt != MBB->end())
-    LoLoop.ToRemove.insert(&*InsertPt);
   LoLoop.ToRemove.insert(Start);
   LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
   return &*MIB;
 }
 
 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
   auto RemovePredicate = [](MachineInstr *MI) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);

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

body:             |
   ; 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
   ; CHECK:   renamable $r3, dead $cpsr = nuw tADDi8 killed renamable $r3, 16, 14 /* CC::al */, $noreg
   ; CHECK:   $lr = MVE_LETP killed renamable $lr, %bb.3
   ; CHECK: bb.4:
   ; CHECK:   successors: %bb.5(0x80000000)
   ; CHECK:   liveins: $q0, $r0, $r1, $r2, $r4
   ; CHECK:   renamable $s4 = nnan ninf nsz VADDS renamable $s0, renamable $s1, 14 /* CC::al */, $noreg
-  ; CHECK:   $lr = t2DLS killed $r4
   ; CHECK:   $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $s4 = nnan ninf nsz VADDS renamable $s2, killed renamable $s4, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $s0 = nnan ninf nsz VADDS killed renamable $s3, killed renamable $s4, 14 /* CC::al */, $noreg, implicit killed $q0
   ; CHECK:   $s2 = VMOVSR $r1, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $s2 = VUITOS killed renamable $s2, 14 /* CC::al */, $noreg
+  ; CHECK:   $lr = t2DLS killed $r4
   ; CHECK:   renamable $s4 = nnan ninf nsz VDIVS killed renamable $s0, killed renamable $s2, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
   ; CHECK: bb.5:
   ; CHECK:   successors: %bb.5(0x7c000000), %bb.6(0x04000000)
   ; CHECK:   liveins: $lr, $q0, $r0, $r1, $r2, $r3, $s4
   ; CHECK:   renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg
   ; CHECK:   $r4 = VMOVRS $s4, 14 /* CC::al */, $noreg
   ; CHECK:   MVE_VPST 2, implicit $vpr

llvm/test/CodeGen/Thumb2/LowOverheadLoops/loop-dec-copy-prev-iteration.mir

body:             |
   ; CHECK:   $lr = t2DLS killed renamable $r3
   ; CHECK:   renamable $r3, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
   ; CHECK: bb.5.bb28:
   ; CHECK:   successors: %bb.5(0x7c000000), %bb.6(0x04000000)
   ; CHECK:   liveins: $lr, $r0, $r1, $r2, $r3, $r8
   ; CHECK:   renamable $r5 = tLDRr renamable $r1, $r3, 14 /* CC::al */, $noreg :: (load 4 from %ir.scevgep617)
   ; CHECK:   renamable $r7, dead $cpsr = tADDrr renamable $r2, renamable $r3, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r6 = tLDRr renamable $r2, $r3, 14 /* CC::al */, $noreg :: (load 4 from %ir.scevgep418)
-  ; CHECK:   dead $r12 = tMOVr $lr, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r8 = nuw t2ADDri killed renamable $r8, 4, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   renamable $r5, dead $cpsr = tEOR killed renamable $r5, killed renamable $r6, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r6 = tLDRr renamable $r0, $r3, 14 /* CC::al */, $noreg :: (load 4 from %ir.scevgep219)
   ; CHECK:   renamable $r5 = nsw tADDhirr killed renamable $r5, killed renamable $r6, 14 /* CC::al */, $noreg
   ; CHECK:   tSTRr killed renamable $r5, renamable $r0, $r3, 14 /* CC::al */, $noreg :: (store 4 into %ir.scevgep219)
   ; CHECK:   renamable $r5, dead $cpsr = tADDrr renamable $r1, renamable $r3, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r4 = tLDRi renamable $r7, 1, 14 /* CC::al */, $noreg :: (load 4 from %ir.scevgep11)
   ; CHECK:   renamable $r6 = tLDRi renamable $r5, 1, 14 /* CC::al */, $noreg :: (load 4 from %ir.scevgep14)

llvm/test/CodeGen/Thumb2/LowOverheadLoops/mov-after-dlstp.mir

body:             |
   ; CHECK:   liveins: $lr, $q0, $r0, $r1, $r2, $r4, $r12
   ; CHECK:   renamable $r12, renamable $q1 = MVE_VLDRWU32_post killed renamable $r12, 16, 0, $noreg :: (load 16 from %ir.pSrc.addr.0.i2, align 4)
   ; CHECK:   renamable $q0 = nnan ninf nsz arcp contract afn reassoc MVE_VADDf32 killed renamable $q0, killed renamable $q1, 0, killed $noreg, killed renamable $q0
   ; CHECK:   $lr = MVE_LETP killed renamable $lr, %bb.1
   ; CHECK: bb.2.arm_mean_f32_mve.exit:
   ; CHECK:   successors: %bb.3(0x80000000)
   ; CHECK:   liveins: $q0, $r0, $r1, $r2, $r4
   ; CHECK:   $s4 = VMOVSR $r1, 14 /* CC::al */, $noreg
-  ; CHECK:   $lr = t2DLS killed $r4
   ; CHECK:   renamable $s0 = nnan ninf nsz arcp contract afn reassoc VADDS killed renamable $s3, killed renamable $s3, 14 /* CC::al */, $noreg, implicit killed $q0
+  ; CHECK:   $lr = t2DLS killed $r4
   ; CHECK:   renamable $s4 = VUITOS killed renamable $s4, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $s0 = nnan ninf nsz arcp contract afn reassoc VDIVS killed renamable $s0, killed renamable $s4, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $r3 = VMOVRS killed renamable $s0, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
   ; CHECK:   renamable $q1 = MVE_VDUP32 killed renamable $r3, 0, $noreg, undef renamable $q1
   ; CHECK:   $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
   ; CHECK: bb.3.do.body:
   ; CHECK:   successors: %bb.3(0x7c000000), %bb.4(0x04000000)

llvm/test/CodeGen/Thumb2/LowOverheadLoops/mov-operand.ll

 ; CHECK-NEXT:    mov r4, lr
 ; CHECK-NEXT:  .LBB0_1: @ %do.body.i
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    vldrw.u32 q1, [r12], #16
 ; CHECK-NEXT:    vadd.f32 q0, q0, q1
 ; CHECK-NEXT:    letp lr, .LBB0_1
 ; CHECK-NEXT:  @ %bb.2: @ %arm_mean_f32_mve.exit
 ; CHECK-NEXT:    vmov s4, r1
-; CHECK-NEXT:    dls lr, r4
 ; CHECK-NEXT:    vadd.f32 s0, s3, s3
 ; CHECK-NEXT:    mov r3, r1
 ; CHECK-NEXT:    vcvt.f32.u32 s4, s4
+; CHECK-NEXT:    dls lr, r4
 ; CHECK-NEXT:    vdiv.f32 s0, s0, s4
 ; CHECK-NEXT:    vmov r12, s0
 ; CHECK-NEXT:    vmov.i32 q0, #0x0
 ; CHECK-NEXT:  .LBB0_3: @ %do.body
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    vctp.32 r3
 ; CHECK-NEXT:    subs r3, #4
 ; CHECK-NEXT:    vpsttt

llvm/test/CodeGen/Thumb2/mve-float32regloops.ll

 ; CHECK-NEXT:    vldrw.u32 q1, [r12]
 ; CHECK-NEXT:    vldr s12, [r0, #8]
 ; CHECK-NEXT:    vdup.32 q2, lr
 ; CHECK-NEXT:    vldr s14, [r0, #16]
 ; CHECK-NEXT:    vstrw.32 q1, [r4]
 ; CHECK-NEXT:    vdup.32 q1, r6
 ; CHECK-NEXT:    mov r6, r2
 ; CHECK-NEXT:    vmov.f32 s6, s12
-; CHECK-NEXT:    dls lr, r3
 ; CHECK-NEXT:    vmov.f32 s10, s14
+; CHECK-NEXT:    dls lr, r3
 ; CHECK-NEXT:    vmov.f32 s7, s12
 ; CHECK-NEXT:    vmov.f32 s11, s14
 ; CHECK-NEXT:  .LBB17_3: @ Parent Loop BB17_2 Depth=1
 ; CHECK-NEXT:    @ => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    vldrw.u32 q4, [r1, q0, uxtw #2]
 ; CHECK-NEXT:    vldrw.u32 q5, [r4, q0, uxtw #2]
 ; CHECK-NEXT:    adds r1, #8
 ; CHECK-NEXT:    vfma.f32 q5, q4, r5