[AMDGPU] Handle isUndef flag in LiveVariables::recomputeForSingleDefVirtReg

[vpykhtin]

Summary

A register's use with isUndef flags shouldn't be considered as a point where the register is live. LiveVariables::runOnInstr ignores such uses.

This was found when I tried to replace calls to

SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion
SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion

with LiveVariables::recomputeForSingleDefVirtReg.

In the testcase below %2 use is undef in the last REG_SEQUENCE.

CodeGen/AMDGPU/si-opt-vgpr-liverange-bug-deadlanes.mir failed:

# After SI Optimize VGPR LiveRange
# Machine code for function _amdgpu_ps_main: IsSSA, TracksLiveness
Function Live Ins: $vgpr0 in %0

bb.0:
  successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)
  liveins: $vgpr0
  %0:vgpr_32 = COPY killed $vgpr0
  %1:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
  %2:vgpr_32 = BUFFER_LOAD_DWORD_OFFEN killed %0:vgpr_32, undef %5:sgpr_128, 0, 0, 0, 0, implicit $exec :: (dereferenceable invariant load (s32))
  %3:sreg_64 = V_CMP_NE_U32_e64 0, %2:vgpr_32, implicit $exec
  %7:sreg_64 = SI_IF killed %3:sreg_64, %bb.2, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
  S_BRANCH %bb.1

bb.1:
; predecessors: %bb.0
  successors: %bb.2(0x80000000); %bb.2(100.00%)

  %8:vreg_128 = REG_SEQUENCE killed %1:vgpr_32, %subreg.sub0, %1:vgpr_32, %subreg.sub1, %1:vgpr_32, %subreg.sub2, undef %4.sub3:vreg_128, %subreg.sub3

bb.2:
; predecessors: %bb.0, %bb.1
  successors: %bb.3(0x40000000), %bb.4(0x40000000); %bb.3(50.00%), %bb.4(50.00%)

  %9:vreg_128 = PHI undef %10:vreg_128, %bb.0, %8:vreg_128, %bb.1
  %14:vgpr_32 = PHI %2:vgpr_32, %bb.0, undef %15:vgpr_32, %bb.1
  %11:sreg_64 = SI_ELSE killed %7:sreg_64, %bb.4, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
  S_BRANCH %bb.3

bb.3:
; predecessors: %bb.2
  successors: %bb.4(0x80000000); %bb.4(100.00%)

  %12:vreg_128 = REG_SEQUENCE killed %14:vgpr_32, %subreg.sub0, %14:vgpr_32, %subreg.sub1, %14:vgpr_32, %subreg.sub2, undef %6:vgpr_32, %subreg.sub3

bb.4:
; predecessors: %bb.2, %bb.3

  %13:vreg_128 = PHI %9:vreg_128, %bb.2, %12:vreg_128, %bb.3
  SI_END_CF killed %11:sreg_64, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
  dead %4:vreg_128 = REG_SEQUENCE killed %13.sub2:vreg_128, %subreg.sub0, %13.sub2:vreg_128, %subreg.sub1, %13.sub2:vreg_128, %subreg.sub2, undef %2:vgpr_32, %subreg.sub3
  S_ENDPGM 0

# End machine code for function _amdgpu_ps_main.

*** Bad machine code: LiveVariables: Block should not be in AliveBlocks ***
- function:    _amdgpu_ps_main
- basic block: %bb.1  (0x55e17ebd7100)
Virtual register %2 is not needed live through the block.

*** Bad machine code: LiveVariables: Block should not be in AliveBlocks ***
- function:    _amdgpu_ps_main
- basic block: %bb.2  (0x55e17ebd7200)
Virtual register %2 is not needed live through the block.

*** Bad machine code: LiveVariables: Block should not be in AliveBlocks ***
- function:    _amdgpu_ps_main
- basic block: %bb.3  (0x55e17ebd7300)
Virtual register %2 is not needed live through the block.

[ruiling]

LGTM

[foad]

LGTM but can you come up with a test case?

[vpykhtin]

• Rebased.
• Added tests.

Tests have revealed another bug:

MachineInstr::readsRegister doesn't check isUndef flag, I've replaced it with readsWritesVirtualRegister(Reg).

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

728

This is just readsVirtualRegister

[vpykhtin]

Replaced MI.readsWritesVirtualRegister(Reg).first with readsVirtualRegister.

[vpykhtin]

llvm/lib/CodeGen/LiveVariables.cpp

728

Thanks!

[foad]

llvm/unittests/MI/LiveIntervalTest.cpp

1

I don't understand this message - does clang-format want you to change something?

[vpykhtin]

llvm/unittests/MI/LiveIntervalTest.cpp

1

It wants me to format most of the source, I didn't include that formatting as would create a lot of unrelated changes.

Maybe it worth to format the entire source after the commit.

[foad]

llvm/unittests/MI/LiveIntervalTest.cpp

1

It wants me to format most of the source

Generally you should run "git clang-format @^" to reformat only the parts that your patch has modified.

[vpykhtin]

llvm/unittests/MI/LiveIntervalTest.cpp

1

Thank you, I didn't know that. I've relied on the formatting of arc diff.

llvm/lib/CodeGen/LiveVariables.cpp

void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) {
 
   VarInfo &VI = getVarInfo(Reg);
   VI.AliveBlocks.clear();
   VI.Kills.clear();
 
   MachineInstr &DefMI = *MRI->getUniqueVRegDef(Reg);
   MachineBasicBlock &DefBB = *DefMI.getParent();
 
-  // Handle the case where all uses have been removed.
-  if (MRI->use_nodbg_empty(Reg)) {
-    VI.Kills.push_back(&DefMI);
-    DefMI.addRegisterDead(Reg, nullptr);
-    return;
-  }
-  DefMI.clearRegisterDeads(Reg);
-
   // Initialize a worklist of BBs that Reg is live-to-end of. (Here
   // "live-to-end" means Reg is live at the end of a block even if it is only
   // live because of phi uses in a successor. This is different from isLiveOut()
   // which does not consider phi uses.)
   SmallVector<MachineBasicBlock *> LiveToEndBlocks;
   SparseBitVector<> UseBlocks;
+  unsigned NumRealUses = 0;
   for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
     UseMO.setIsKill(false);
+    if (!UseMO.readsReg())
+      continue;
+    ++NumRealUses;
     MachineInstr &UseMI = *UseMO.getParent();
     MachineBasicBlock &UseBB = *UseMI.getParent();
     UseBlocks.set(UseBB.getNumber());
     if (UseMI.isPHI()) {
       // If Reg is used in a phi then it is live-to-end of the corresponding
       // predecessor.
       unsigned Idx = UseMO.getOperandNo();
       LiveToEndBlocks.push_back(UseMI.getOperand(Idx + 1).getMBB());
     } else if (&UseBB == &DefBB) {
       // A non-phi use in the same BB as the single def must come after the def.
     } else {
       // Otherwise Reg must be live-to-end of all predecessors.
       LiveToEndBlocks.append(UseBB.pred_begin(), UseBB.pred_end());
     }
   }
 
+  // Handle the case where all uses have been removed.
+  if (NumRealUses == 0) {
+    VI.Kills.push_back(&DefMI);
+    DefMI.addRegisterDead(Reg, nullptr);
+    return;
+  }
+  DefMI.clearRegisterDeads(Reg);
+
   // Iterate over the worklist adding blocks to AliveBlocks.
   bool LiveToEndOfDefBB = false;
   while (!LiveToEndBlocks.empty()) {
     MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val();
     if (&BB == &DefBB) {
       LiveToEndOfDefBB = true;
       continue;
     }
for (unsigned UseBBNum : UseBlocks) {
     MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum);
     if (&UseBB == &DefBB && LiveToEndOfDefBB)
       continue;
     for (auto &MI : reverse(UseBB)) {
       if (MI.isDebugOrPseudoInstr())
         continue;
       if (MI.isPHI())
         break;
-      if (MI.readsRegister(Reg)) {
+      if (MI.readsVirtualRegister(Reg)) {
         assert(!MI.killsRegister(Reg));
         MI.addRegisterKilled(Reg, nullptr);
         VI.Kills.push_back(&MI);
         break;
       }
     }
   }
 }

llvm/unittests/MI/LiveIntervalTest.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/LiveIntervals.h"
+#include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MIRParser/MIRParser.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/TargetRegistry.h"
std::unique_ptr<Module> parseMIR(LLVMContext &Context,
   MachineModuleInfoWrapperPass *MMIWP = new MachineModuleInfoWrapperPass(&TM);
   if (MIR->parseMachineFunctions(*M, MMIWP->getMMI()))
     return nullptr;
   PM.add(MMIWP);
 
   return M;
 }
 
-typedef std::function<void(MachineFunction&,LiveIntervals&)> LiveIntervalTest;
-
 struct TestPass : public MachineFunctionPass {
   static char ID;
-  TestPass() : MachineFunctionPass(ID) {
+  TestPass() : MachineFunctionPass(ID) {}
+};
+
+template <typename AnalysisType>
+struct TestPassT : public TestPass {
+
+  typedef std::function<void(MachineFunction&,AnalysisType&)> TestFx;
+
+  TestPassT() {
     // We should never call this but always use PM.add(new TestPass(...))
     abort();
   }
-  TestPass(LiveIntervalTest T, bool ShouldPass)
-      : MachineFunctionPass(ID), T(T), ShouldPass(ShouldPass) {
+  TestPassT(TestFx T, bool ShouldPass)
+      : T(T), ShouldPass(ShouldPass) {
     initializeTestPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override {
-    LiveIntervals &LIS = getAnalysis<LiveIntervals>();
-    T(MF, LIS);
+    AnalysisType &A = getAnalysis<AnalysisType>();
+    T(MF, A);
     EXPECT_EQ(MF.verify(this, /* Banner */ nullptr, /* AbortOnError */ false),
               ShouldPass);
     return true;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
-    AU.addRequired<LiveIntervals>();
-    AU.addPreserved<LiveIntervals>();
+    AU.addRequired<AnalysisType>();
+    AU.addPreserved<AnalysisType>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 private:
-  LiveIntervalTest T;
+  TestFx T;
   bool ShouldPass;
 };
 
 static MachineInstr &getMI(MachineFunction &MF, unsigned At,
                            unsigned BlockNum) {
   MachineBasicBlock &MBB = *MF.getBlockNumbered(BlockNum);
 
   unsigned I = 0;
static bool checkRegUnitInterference(LiveIntervals &LIS,
   for (MCRegUnit Unit : TRI.regunits(PhysReg)) {
     const LiveRange &UnitRange = LIS.getRegUnit(Unit);
     if (VirtReg.overlaps(UnitRange, CP, *LIS.getSlotIndexes()))
       return true;
   }
   return false;
 }
 
-static void liveIntervalTest(StringRef MIRFunc, LiveIntervalTest T,
-                             bool ShouldPass = true) {
+template <typename AnalysisType>
+static void doTest(StringRef MIRFunc,
+                   typename TestPassT<AnalysisType>::TestFx T,
   LLVMContext Context;
   std::unique_ptr<LLVMTargetMachine> TM = createTargetMachine();
   // This test is designed for the X86 backend; stop if it is not available.
   if (!TM)
     return;
 
   legacy::PassManager PM;
+  std::unique_ptr<MIRParser> MIR;
+  std::unique_ptr<Module> M = parseMIR(Context, PM, MIR, *TM, MIRFunc, "func");
+  ASSERT_TRUE(M);
+
+  PM.add(new TestPassT<AnalysisType>(T, ShouldPass));
+
+  PM.run(*M);
+}
 
+static void liveIntervalTest(StringRef MIRFunc,
+                             TestPassT<LiveIntervals>::TestFx T,
+                             bool ShouldPass = true) {
   SmallString<160> S;
   StringRef MIRString = (Twine(R"MIR(
 ---
 ...
 name: func
 registers:
   - { id: 0, class: sreg_64 }
 body: |
   bb.0:
 )MIR") + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
-  std::unique_ptr<MIRParser> MIR;
-  std::unique_ptr<Module> M = parseMIR(Context, PM, MIR, *TM, MIRString,
-                                       "func");
-  ASSERT_TRUE(M);
 
-  PM.add(new TestPass(T, ShouldPass));
+  doTest<LiveIntervals>(MIRString, T, ShouldPass);
+}
 
-  PM.run(*M);
+static void liveVariablesTest(StringRef MIRFunc,
+                             TestPassT<LiveVariables>::TestFx T,
+                             bool ShouldPass = true) {
+  SmallString<160> S;
+  StringRef MIRString = (Twine(R"MIR(
+---
+...
+name: func
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_64 }
+body: |
+  bb.0:
+)MIR") + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
+  doTest<LiveVariables>(MIRString, T, ShouldPass);
 }
 
 } // End of anonymous namespace.
 
 char TestPass::ID = 0;
 INITIALIZE_PASS(TestPass, "testpass", "testpass", false, false)
 
 TEST(LiveIntervalTest, MoveUpDef) {
)MIR",
 
         SlotIndex NewIdx = LIS.getInstructionIndex(ImpDef).getRegSlot();
         FirstSeg->start = NewIdx;
         FirstSeg->valno->def = NewIdx;
       },
       false);
 }
 
+TEST(LiveVariablesTest, recomputeForSingleDefVirtReg_handle_undef1) {
+  liveVariablesTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0, implicit %0
+    S_NOP 0, implicit undef %0
+)MIR", [](MachineFunction &MF, LiveVariables &LV) {
+     auto &FirstNop = getMI(MF, 1, 0);
+     auto &SecondNop = getMI(MF, 2, 0);
+     EXPECT_TRUE(FirstNop.getOperand(1).isKill());
+     EXPECT_FALSE(SecondNop.getOperand(1).isKill());
+
+     Register R = Register::index2VirtReg(0);
+     LV.recomputeForSingleDefVirtReg(R);
+
+     EXPECT_TRUE(FirstNop.getOperand(1).isKill());
+     EXPECT_FALSE(SecondNop.getOperand(1).isKill());
+  });
+}
+
+TEST(LiveVariablesTest, recomputeForSingleDefVirtReg_handle_undef2) {
+  liveVariablesTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0, implicit %0
+    S_NOP 0, implicit undef %0, implicit %0
+)MIR", [](MachineFunction &MF, LiveVariables &LV) {
+     auto &FirstNop = getMI(MF, 1, 0);
+     auto &SecondNop = getMI(MF, 2, 0);
+     EXPECT_FALSE(FirstNop.getOperand(1).isKill());
+     EXPECT_FALSE(SecondNop.getOperand(1).isKill());
+     EXPECT_TRUE(SecondNop.getOperand(2).isKill());
+
+     Register R = Register::index2VirtReg(0);
+     LV.recomputeForSingleDefVirtReg(R);
+
+     EXPECT_FALSE(FirstNop.getOperand(1).isKill());
+     EXPECT_FALSE(SecondNop.getOperand(1).isKill());
+     EXPECT_TRUE(SecondNop.getOperand(2).isKill());
+  });
+}
+
 int main(int argc, char **argv) {
   ::testing::InitGoogleTest(&argc, argv);
   initLLVM();
   return RUN_ALL_TESTS();
 }