[ARM][LowOverheadLoops] Don't generate a LOL if lr is redefined after the start

[samtebbs]

Summary

Low-overhead loops are created even if the LR is redefined after the loop start instruction, causing the loop decrement and loop end to use different values to the loop start. This patch makes sure that the LR definition at the loop start is the same as the live-out def.

[dmgreen]

I think we may need to alter the way this works to make it so that things like this ideally can't happen. I've been trying to change it so that t2LoopStart looks like:

$lr = t2DoLoopStart renamable $rn

as opposed to

t2DoLoopStart renamable $rn

That I hope should glue this together better and mean that we can rely on lr always being the correct value to use at least at the start instruction, and we don't need to revert as often. But there are a lot of tests to update :-/

[samparker]

$lr = t2DoLoopStart renamable $rn

+1

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

1064–1070

I think what we need to do is check that the value is live-in the loop header block. Which makes the current call to if (!RDA.isSafeToDefRegAt(Start, ARM::LR)) seem bogus and is probably there to catch when WhileLoopStart is in the header and the mov lr is in the preheader. With Dave's work on DLS, most of this mumbo jumbo will get removed, but we still need to ensure we can insert a WLS safely, which is what this check should be doing.

[samtebbs]

Thanks for the review. I will delay working on this until @dmgreen 's lr patch is in as it affect fix this.

[samtebbs]

Rebase

[samparker]

So my thoughts:

• For the case where LRDef is not null, we should be able to check that this same value is used by 'Dec'. That way we have proved explicitly the the use-def chain is correct instead of relying on the check of the live-out value.
• For any the case where LRDef is null, I'm pretty sure we just need to try harder to find it - something needs to be setting LR for loop entry.
• My issue with the isSafeToDefRegAt is that is a local check. If WLS is in the preheader predecessor, we could decide we that defining LR is safe (locally), but then LR is redefined in the preheader.

So looks like two patches to me: modify the current one to find the explicit use-def chain, and then another to prove WLS safety. I reckon you could make a copy of your test and change it to use a WLS to show that we've got a bug.

[dmgreen]

When can this happen now? We added lr as a def of t2DoLoopStart so this kind of thing would not be possible, and we would not need to do this expensive / impossible checking so late in the backend, where it is so difficult to get really correct.

[samparker]

I'd be happy with an assertion that DoLoopStart is connected properly, but WhileLoopStart is still my real concern with this logic.

[samtebbs]

Abandoning this for now as the code and logic this is based on has been improved and updated. I'll revisit it if it ends up still being an issue.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

 //===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// Finalize v8.1-m low-overhead loops by converting the associated pseudo
if (Start->getOpcode() == ARM::t2WhileLoopStart &&
       LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
       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,
                                     InstSet &ToRemove) {
-    // For a t2DoLoopStart it is always valid to use the start insertion point.
+    // For a t2DoLoopStart it is always valid to use the start insertion
+    // point, as long as there is no redefinition of LR after the Start
     // For WLS we can define LR if LR already contains the same value.
     if (isDo(Start) || Start->getOperand(0).getReg() == ARM::LR) {
+      auto *LRDef = RDA.getLocalLiveOutMIDef(Start->getParent(), ARM::LR);
+      if (LRDef == nullptr ||
+        RDA.getUniqueReachingMIDef(Start, ARM::LR) == LRDef) {
         InsertPt = MachineBasicBlock::iterator(Start);
         InsertBB = Start->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, MCRegister::from(ARM::LR)))
       return false;
 
     InsertPt = MachineBasicBlock::iterator(Start);
     InsertBB = Start->getParent();

llvm/test/CodeGen/Thumb2/LowOverheadLoops/lr-def-after-start.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=thumbv8.1m.main-none-none-eabi -mattr=+mve -run-pass=arm-low-overhead-loops %s -o - | FileCheck %s
+
+--- |
+  define arm_aapcs_vfpcc void @do_loop_start_kills_reg(float* %pSrc, i32 %blockSize, float* nocapture %pResult) {
+  entry:
+    ret void
+  }
+...
+---
+name:            do_loop_start_kills_reg
+alignment:       2
+tracksRegLiveness: true
+registers:       []
+liveins:
+  - { reg: '$r0', virtual-reg: '' }
+  - { reg: '$r1', virtual-reg: '' }
+  - { reg: '$r2', virtual-reg: '' }
+frameInfo:
+  stackSize:       8
+  offsetAdjustment: 0
+  maxAlignment:    4
+fixedStack:      []
+stack:
+  - { id: 0, name: '', type: spill-slot, offset: -4, size: 4, alignment: 4,
+      stack-id: default, callee-saved-register: '$lr', callee-saved-restored: false,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { 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: '' }
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: do_loop_start_kills_reg
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; 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:   $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
+  ; CHECK:   tCMPi8 renamable $r1, 4, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 10, 8, implicit-def $itstate
+  ; CHECK:   renamable $r3 = tMOVi8 $noreg, 4, 10 /* CC::ge */, killed $cpsr, implicit killed renamable $r3, implicit killed $itstate
+  ; CHECK:   renamable $r12 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   renamable $r3, dead $cpsr = tSUBrr renamable $r1, killed renamable $r3, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
+  ; CHECK:   renamable $r3, dead $cpsr = tADDi8 killed renamable $r3, 3, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $lr = nuw nsw t2ADDrs killed renamable $r12, killed renamable $r3, 19, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
+  ; CHECK:   $r12 = tMOVr killed $r0, 14 /* CC::al */, $noreg
+  ; CHECK:   dead $lr = tMOVr killed renamable $lr, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $lr = tMOVr $r2, 14 /* CC::al */, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x7c000000), %bb.2(0x04000000)
+  ; CHECK:   liveins: $lr, $q0, $r1, $r2, $r3, $r12
+  ; CHECK:   renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg
+  ; CHECK:   renamable $r3, dead $cpsr = tSUBi8 killed renamable $r3, 4, 14 /* CC::al */, $noreg
+  ; CHECK:   $lr = t2SUBri killed renamable $lr, 1, 14 /* CC::al */, $noreg, def $cpsr
+  ; CHECK:   MVE_VPST 4, implicit $vpr
+  ; CHECK:   renamable $r12, renamable $q1 = MVE_VLDRWU32_post killed renamable $r12, 16, 1, renamable $vpr
+  ; CHECK:   renamable $q0 = MVE_VADDf32 killed renamable $q0, killed renamable $q1, 1, killed renamable $vpr, killed renamable $q0
+  ; CHECK:   tBcc %bb.1, 1 /* CC::ne */, killed $cpsr
+  ; CHECK:   tB %bb.2, 14 /* CC::al */, $noreg
+  ; CHECK: bb.2:
+  ; CHECK:   liveins: $q0, $r1, $r2
+  ; CHECK:   renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 1, 14 /* CC::al */, $noreg
+  ; 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:   $s2 = VMOVSR killed $r0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $s2 = VUITOS killed renamable $s2, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $s0 = nnan ninf nsz arcp contract afn reassoc VDIVS killed renamable $s0, killed renamable $s2, 14 /* CC::al */, $noreg
+  ; CHECK:   VSTRS killed renamable $s0, killed renamable $r2, 0, 14 /* CC::al */, $noreg :: (store 4 into %ir.pResult)
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r4, def $pc
+  bb.0:
+    successors: %bb.1(0x80000000)
+    liveins: $r0, $r1, $r2, $r4, $lr
+
+    frame-setup tPUSH 14 /* CC::al */, $noreg, $r4, killed $lr, implicit-def $sp, implicit $sp
+    frame-setup CFI_INSTRUCTION def_cfa_offset 8
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r4, -8
+    $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
+    tCMPi8 renamable $r1, 4, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 10, 8, implicit-def $itstate
+    renamable $r3 = tMOVi8 $noreg, 4, 10 /* CC::ge */, killed $cpsr, implicit killed renamable $r3, implicit killed $itstate
+    renamable $r12 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+    renamable $r3, dead $cpsr = tSUBrr renamable $r1, killed renamable $r3, 14 /* CC::al */, $noreg
+    renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
+    renamable $r3, dead $cpsr = tADDi8 killed renamable $r3, 3, 14 /* CC::al */, $noreg
+    renamable $lr = nuw nsw t2ADDrs killed renamable $r12, killed renamable $r3, 19, 14 /* CC::al */, $noreg, $noreg
+    $r3 = tMOVr $r1, 14 /* CC::al */, $noreg
+    $r12 = tMOVr $r0, 14 /* CC::al */, $noreg
+    dead $lr = t2DoLoopStart killed renamable $lr
+    renamable $lr = tMOVr $r2, 14 /* CC::al */, $noreg
+
+  bb.1:
+    successors: %bb.1(0x7c000000), %bb.4(0x04000000)
+    liveins: $lr, $q0, $r0, $r1, $r2, $r3, $r4, $r12, $lr
+
+    renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg
+    renamable $r3, dead $cpsr = tSUBi8 killed renamable $r3, 4, 14 /* CC::al */, $noreg
+    renamable $lr = t2LoopDec renamable $lr, 1
+    MVE_VPST 4, implicit $vpr
+    renamable $r12, renamable $q1 = MVE_VLDRWU32_post killed renamable $r12, 16, 1, renamable $vpr
+    renamable $q0 = MVE_VADDf32 killed renamable $q0, killed renamable $q1, 1, killed renamable $vpr, renamable $q0
+    t2LoopEnd renamable $lr, %bb.1, implicit-def dead $cpsr
+    tB %bb.4, 14 /* CC::al */, $noreg
+
+  bb.4:
+    liveins: $q0, $r1, $r2
+
+    renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 1, 14 /* CC::al */, $noreg
+    renamable $s0 = nnan ninf nsz arcp contract afn reassoc VADDS killed renamable $s3, renamable $s3, 14 /* CC::al */, $noreg, implicit $q0
+    $s2 = VMOVSR killed $r0, 14 /* CC::al */, $noreg
+    renamable $s2 = VUITOS killed renamable $s2, 14 /* CC::al */, $noreg
+    renamable $s0 = nnan ninf nsz arcp contract afn reassoc VDIVS killed renamable $s0, killed renamable $s2, 14 /* CC::al */, $noreg
+    VSTRS killed renamable $s0, killed renamable $r2, 0, 14 /* CC::al */, $noreg :: (store 4 into %ir.pResult)
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r4, def $pc
+
+...
+