[AMDGPU] Really preserve LiveVariables in SILowerControlFlow

[foad]

Summary

https://bugs.llvm.org/show_bug.cgi?id=52204

[foad]

Also update Kills based on existing kill flags.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

672

You need to re-compute Kills as well.

686

This sounds like true after Phi elimination? I did not do careful thinking. But it is not true when we have PHI, see the pattern described at line 148 in this file.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

691

The caller is required to correctly set the isKill flag before calling this function?

[foad]

Handle phi nodes. Add new dead/kill flags.

[arsenm]

llvm/include/llvm/CodeGen/LiveVariables.h

193

Typo nocessary

llvm/lib/CodeGen/LiveVariables.cpp

731–732

Won't this do the right thing if you unconditionally call addRegisterKilled?

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

722

Does this work for phi uses? I'm not sure.

731–732

It could give you duplicate entries in the Kills vector which seems undesirable.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

672

liveness sounds unnecessary to me. It is better to explicitly say this is for virtual register to align with other public functions of LiveVariables. Something like recomputeForSingleDefVirtReg()?

695–699

This is not quite accurate. if the user is a PHI. we need to handle differently if the user appears in the same block as the define block.

For the pattern drawn at line 148 (incoming block is the same as define block), we don't treat the Reg is alive through the incoming block, it is only alive from the definition to the end. If the incoming block is different from define block, we need to mark the Reg is alive through the incoming block.

731

I think you don't need to require that the isKill flag was correctly setup before calling this function, finding out the new kill after modification is a non-trivial work for general case. It is really handy to find the kill instructions here. Doing a reverse iteration over the instructions will just give you the kill instruction, that is the first instruction we meet.
You can just remove the killsRegister() check here and also stop pushing into Kills when iterating over the uses earlier in this function .

[foad]

Rename function. Recompute dead/kill flags from scratch.

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

695–699

I think my code is correct. I am only saying it is live-out of the corresponding predecessor, not live-through. The "Iterate ..." loop below handles the case where Reg is live-out of DefBB.

[foad]

Add dead def MI to Kills. Do not add phi nodes to Kills.

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

722

As explained in the comment on struct VarInfo, phi nodes should not be included in Kills, and I think that means that LiveVariables never sets the killed flag on phi use operands.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

695–699

I see the problem, your interpretation of live-out does not match what it means in LLVM. You can take a look at LiveVariables::isLiveOut(). We are not saying that a register is live-out of a block if it is only used by a PHI in successor block. I would suggest renaming LiveOutBlocks to LiveToEndBlocks. So we don't have conflicting interpretations of live-out. Please also fix the use of live-out in comments.

[foad]

Change terminology.

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

695–699

Thanks for explaining. I fixed it, but I still think my terminology is better :)

The way I think of it is that phi uses occur on an edge between two blocks. A phi use still means that the value is live-out of the predecessor, since it happens after the end of the predecessor (and before the start of the successor).

[ruiling]

To the best of my knowledge, the change looks good. But wait one or two days in case others may have more comments. And one corner case which I think also needs to be updated.

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

719–720

Here I think the use of InputReg can be a possible kill. Actually we should inherit the possible KILL state from original pseudo instruction. and also replace the Kills of InputReg.

[foad]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

719–720

The problem here is that we are inserting new instructions in a different place from the original SI_INIT_EXEC_FROM_INPUT instruction. For example, before this pass:

bb.0.main_body:
  liveins: $sgpr0, $vgpr0
  %1:vgpr_32 = COPY killed $vgpr0
  %0:sgpr_32 = COPY killed $sgpr0
  %3:vgpr_32 = V_ADD_U32_e32 %0:sgpr_32, killed %1:vgpr_32, implicit $exec
  %4:vgpr_32 = V_CVT_F32_I32_e32 killed %3:vgpr_32, implicit $mode, implicit $exec
  SI_INIT_EXEC_FROM_INPUT killed %0:sgpr_32, 19, implicit-def dead $exec
  $vgpr0 = COPY killed %4:vgpr_32
  SI_RETURN_TO_EPILOG killed $vgpr0

Note that SI_INIT_EXEC_FROM_INPUT kills %0. But if we copy the kill flag to the S_BFE_U32 instruction we get this:

bb.0.main_body:
  liveins: $sgpr0, $vgpr0
  %0:sgpr_32 = COPY killed $sgpr0
  %5:sgpr_32 = S_BFE_U32 killed %0:sgpr_32, 458771, implicit-def $scc
  $exec = S_BFM_B64 %5:sgpr_32, 0
  S_CMP_EQ_U32 killed %5:sgpr_32, 64, implicit-def $scc
  $exec = S_CMOV_B64 -1, implicit $scc
  %1:vgpr_32 = COPY killed $vgpr0
  %3:vgpr_32 = V_ADD_U32_e32 %0:sgpr_32, killed %1:vgpr_32, implicit $exec
  %4:vgpr_32 = V_CVT_F32_I32_e32 killed %3:vgpr_32, implicit $mode, implicit $exec
  $vgpr0 = COPY killed %4:vgpr_32
  SI_RETURN_TO_EPILOG killed $vgpr0

which is wrong, because %0 is used in the V_ADD_U32 instruction after the kill.

What do you think we should do here? Is it OK to drop the kill flag?

[foad]

Recompute for InputReg in SILowerControlFlow::lowerInitExec.
Fix adding kills in DefBB.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

732

why do we need this?

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

719–720

I did not notice that, re-computing like in this new version sounds good idea.

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

732

This is the cheapest way I could think of to test whether Reg is live-to-end of DefBB. Note that DefBB never appears in AliveBlocks.

[ruiling]

llvm/lib/CodeGen/LiveVariables.cpp

729

I would suggest you check against LiveToEndBlocks instead of AliveBlocks.
Think of one possible situation:
bb0:

%1 = ...

bb1:

... = phi [%1 %bb0], [%2 %bb1]
%2 = ...
 ... = add %2, 1
 br i1 %x, bb1, bb2

The add instruction at bb1 that reads %2 should not be marked as KILL. Sounds like we are not doing it right currently.

732

Does my comment above sound good to you? UseBlocks.count() == 1 does not mean whether the Reg is live-to-end of DefBB.

[foad]

Fix check for live-to-end of DefBB.

[foad]

llvm/lib/CodeGen/LiveVariables.cpp

732

You are right of course. I can't use LiveToEndBlocks directly because it is a worklist, and it is empty here, so I introduced a new boolean flag for this.

[ruiling]

sounds good to me.

[foad]

@ruiling thanks for the careful review!

llvm/include/llvm/CodeGen/LiveVariables.h

public:
 
   /// RegisterDefIsDead - Return true if the specified instruction defines the
   /// specified register, but that definition is dead.
   bool RegisterDefIsDead(MachineInstr &MI, Register Reg) const;
 
   //===--------------------------------------------------------------------===//
   //  API to update live variable information
 
+  /// Recompute liveness from scratch for a virtual register \p Reg that is
+  /// known to have a single def that dominates all uses. This can be useful
+  /// after removing some uses of \p Reg. It is not necessary for the whole
+  /// machine function to be in SSA form.
+  void recomputeForSingleDefVirtReg(Register Reg);
+
   /// replaceKillInstruction - Update register kill info by replacing a kill
   /// instruction with a new one.
   void replaceKillInstruction(Register Reg, MachineInstr &OldMI,
                               MachineInstr &NewMI);
 
   /// addVirtualRegisterKilled - Add information about the fact that the
   /// specified register is killed after being used by the specified
   /// instruction. If AddIfNotFound is true, add a implicit operand if it's

llvm/lib/CodeGen/LiveVariables.cpp

#endif
 
   PhysRegDef.clear();
   PhysRegUse.clear();
   PHIVarInfo.clear();
 
   return false;
 }
 
+void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) {
+  assert(Reg.isVirtual());
+
+  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;
+  for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
+    UseMO.setIsKill(false);
+    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 = UseMI.getOperandNo(&UseMO);
+      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());
+    }
+  }
+
+  // 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;
+    }
+    if (VI.AliveBlocks.test(BB.getNumber()))
+      continue;
+    VI.AliveBlocks.set(BB.getNumber());
+    LiveToEndBlocks.append(BB.pred_begin(), BB.pred_end());
+  }
+
+  // Recompute kill flags. For each block in which Reg is used but is not
+  // live-through, find the last instruction that uses Reg. Ignore phi nodes
+  // because they should not be included in Kills.
+  for (unsigned UseBBNum : UseBlocks) {
+    if (VI.AliveBlocks.test(UseBBNum))
+      continue;
+    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)) {
+        assert(!MI.killsRegister(Reg));
+        MI.addRegisterKilled(Reg, nullptr);
+        VI.Kills.push_back(&MI);
+        break;
+      }
+    }
+  }
+}
+
 /// replaceKillInstruction - Update register kill info by replacing a kill
 /// instruction with a new one.
 void LiveVariables::replaceKillInstruction(Register Reg, MachineInstr &OldMI,
                                            MachineInstr &NewMI) {
   VarInfo &VI = getVarInfo(Reg);
   std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
 }
 

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

 /// %exec = S_OR_B64 %exec, %sgpr0     // Re-enable saved exec mask bits
 //===----------------------------------------------------------------------===//
 
 #include "AMDGPU.h"
 #include "GCNSubtarget.h"
 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LiveIntervals.h"
+#include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "si-lower-control-flow"
 
 static cl::opt<bool>
 RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
     cl::init(true), cl::ReallyHidden);
 
 namespace {
 
 class SILowerControlFlow : public MachineFunctionPass {
 private:
   const SIRegisterInfo *TRI = nullptr;
   const SIInstrInfo *TII = nullptr;
   LiveIntervals *LIS = nullptr;
+  LiveVariables *LV = nullptr;
   MachineDominatorTree *MDT = nullptr;
   MachineRegisterInfo *MRI = nullptr;
   SetVector<MachineInstr*> LoweredEndCf;
   DenseSet<Register> LoweredIf;
   SmallSet<MachineBasicBlock *, 4> KillBlocks;
 
   const TargetRegisterClass *BoolRC = nullptr;
   unsigned AndOpc;
void SILowerControlFlow::emitIf(MachineInstr &MI) {
   LoweredIf.insert(CopyReg);
 
   Register Tmp = MRI->createVirtualRegister(BoolRC);
 
   MachineInstr *And =
     BuildMI(MBB, I, DL, TII->get(AndOpc), Tmp)
     .addReg(CopyReg)
     .add(Cond);
+  if (LV)
+    LV->replaceKillInstruction(Cond.getReg(), MI, *And);
 
   setImpSCCDefDead(*And, true);
 
   MachineInstr *Xor = nullptr;
   if (!SimpleIf) {
     Xor =
       BuildMI(MBB, I, DL, TII->get(XorOpc), SaveExecReg)
       .addReg(Tmp)
       .addReg(CopyReg);
     setImpSCCDefDead(*Xor, ImpDefSCC.isDead());
   }
 
   // Use a copy that is a terminator to get correct spill code placement it with
   // fast regalloc.
   MachineInstr *SetExec =
     BuildMI(MBB, I, DL, TII->get(MovTermOpc), Exec)
     .addReg(Tmp, RegState::Kill);
+  if (LV)
+    LV->getVarInfo(Tmp).Kills.push_back(SetExec);
 
   // Skip ahead to the unconditional branch in case there are other terminators
   // present.
   I = skipToUncondBrOrEnd(MBB, I);
 
   // Insert the S_CBRANCH_EXECZ instruction which will be optimized later
   // during SIRemoveShortExecBranches.
   MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
void SILowerControlFlow::emitElse(MachineInstr &MI) {
   MachineBasicBlock::iterator Start = MBB.begin();
 
   // This must be inserted before phis and any spill code inserted before the
   // else.
   Register SaveReg = MRI->createVirtualRegister(BoolRC);
   MachineInstr *OrSaveExec =
     BuildMI(MBB, Start, DL, TII->get(OrSaveExecOpc), SaveReg)
     .add(MI.getOperand(1)); // Saved EXEC
+  if (LV)
+    LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *OrSaveExec);
 
   MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();
 
   MachineBasicBlock::iterator ElsePt(MI);
 
   // This accounts for any modification of the EXEC mask within the block and
   // can be optimized out pre-RA when not required.
   MachineInstr *And = BuildMI(MBB, ElsePt, DL, TII->get(AndOpc), DstReg)
void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
   // AND the break condition operand with exec, then OR that into the "loop
   // exit" mask.
   MachineInstr *And = nullptr, *Or = nullptr;
   if (!SkipAnding) {
     Register AndReg = MRI->createVirtualRegister(BoolRC);
     And = BuildMI(MBB, &MI, DL, TII->get(AndOpc), AndReg)
              .addReg(Exec)
              .add(MI.getOperand(1));
+    if (LV)
+      LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *And);
     Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
              .addReg(AndReg)
              .add(MI.getOperand(2));
     if (LIS)
       LIS->createAndComputeVirtRegInterval(AndReg);
-  } else
+  } else {
     Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
              .add(MI.getOperand(1))
              .add(MI.getOperand(2));
+    if (LV)
+      LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *Or);
+  }
+  if (LV)
+    LV->replaceKillInstruction(MI.getOperand(2).getReg(), MI, *Or);
 
   if (LIS) {
     if (And)
       LIS->InsertMachineInstrInMaps(*And);
     LIS->ReplaceMachineInstrInMaps(MI, *Or);
   }
 
   MI.eraseFromParent();
if (NeedBlockSplit) {
     Opcode = OrTermrOpc;
     InsPt = MI;
   }
 
   MachineInstr *NewMI =
     BuildMI(MBB, InsPt, DL, TII->get(Opcode), Exec)
     .addReg(Exec)
     .add(MI.getOperand(0));
+  if (LV)
+    LV->replaceKillInstruction(MI.getOperand(0).getReg(), MI, *NewMI);
 
   LoweredEndCf.insert(NewMI);
 
   if (LIS)
     LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
 
   MI.eraseFromParent();
 
Register SavedExec
       = TII->getNamedOperand(*Next, AMDGPU::OpName::src1)->getReg();
     assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
 
     const MachineInstr *Def = MRI->getUniqueVRegDef(SavedExec);
     if (Def && LoweredIf.count(SavedExec)) {
       LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
       if (LIS)
         LIS->RemoveMachineInstrFromMaps(*MI);
+      Register Reg;
+      if (LV)
+        Reg = TII->getNamedOperand(*MI, AMDGPU::OpName::src1)->getReg();
       MI->eraseFromParent();
+      if (LV)
+        LV->recomputeForSingleDefVirtReg(Reg);
       removeMBBifRedundant(MBB);
     }
   }
 }
 
 MachineBasicBlock *SILowerControlFlow::process(MachineInstr &MI) {
   MachineBasicBlock &MBB = *MI.getParent();
   MachineBasicBlock::iterator I(MI);
if (InputReg.isVirtual()) {
     }
   }
 
   // Insert instruction sequence at block beginning (before vector operations).
   const DebugLoc DL = MI.getDebugLoc();
   const unsigned WavefrontSize = ST.getWavefrontSize();
   const unsigned Mask = (WavefrontSize << 1) - 1;
   Register CountReg = MRI->createVirtualRegister(&AMDGPU::SGPR_32RegClass);
   auto BfeMI = BuildMI(*MBB, FirstMI, DL, TII->get(AMDGPU::S_BFE_U32), CountReg)
                    .addReg(InputReg)
                    .addImm((MI.getOperand(1).getImm() & Mask) | 0x70000);
+  if (LV)
+    LV->recomputeForSingleDefVirtReg(InputReg);
   auto BfmMI =
       BuildMI(*MBB, FirstMI, DL,
               TII->get(IsWave32 ? AMDGPU::S_BFM_B32 : AMDGPU::S_BFM_B64), Exec)
           .addReg(CountReg)
           .addImm(0);
   auto CmpMI = BuildMI(*MBB, FirstMI, DL, TII->get(AMDGPU::S_CMP_EQ_U32))
                    .addReg(CountReg, RegState::Kill)
                    .addImm(WavefrontSize);
+  if (LV)
+    LV->getVarInfo(CountReg).Kills.push_back(CmpMI);
   auto CmovMI =
       BuildMI(*MBB, FirstMI, DL,
               TII->get(IsWave32 ? AMDGPU::S_CMOV_B32 : AMDGPU::S_CMOV_B64),
               Exec)
           .addImm(-1);
 
   if (!LIS) {
     MI.eraseFromParent();
if (!Succ->canFallThrough()) {
               FallThrough->findBranchDebugLoc(), TII->get(AMDGPU::S_BRANCH))
           .addMBB(Succ);
   }
 
   return true;
 }
 
 bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
-  // FIXME: This pass causes verification failures.
-  // See: https://bugs.llvm.org/show_bug.cgi?id=52204
-  MF.getProperties().set(
-      MachineFunctionProperties::Property::FailsVerification);
-
   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
   TII = ST.getInstrInfo();
   TRI = &TII->getRegisterInfo();
 
   // This doesn't actually need LiveIntervals, but we can preserve them.
   LIS = getAnalysisIfAvailable<LiveIntervals>();
+  // This doesn't actually need LiveVariables, but we can preserve them.
+  LV = getAnalysisIfAvailable<LiveVariables>();
   MDT = getAnalysisIfAvailable<MachineDominatorTree>();
   MRI = &MF.getRegInfo();
   BoolRC = TRI->getBoolRC();
 
   if (ST.isWave32()) {
     AndOpc = AMDGPU::S_AND_B32;
     OrOpc = AMDGPU::S_OR_B32;
     XorOpc = AMDGPU::S_XOR_B32;

llvm/lib/Target/AMDGPU/SIWholeQuadMode.cpp

default:
       continue;
     }
     if (SplitPoint)
       splitBlock(MBB, SplitPoint);
   }
 }
 
 bool SIWholeQuadMode::runOnMachineFunction(MachineFunction &MF) {
-  // This pass is a convenient place to re-enable machine verification after the
-  // problems caused by SILowerControlFlow have been fixed.
-  MF.getProperties().reset(
-      MachineFunctionProperties::Property::FailsVerification);
-
   LLVM_DEBUG(dbgs() << "SI Whole Quad Mode on " << MF.getName()
                     << " ------------- \n");
   LLVM_DEBUG(MF.dump(););
 
   Instructions.clear();
   Blocks.clear();
   LiveMaskQueries.clear();
   LowerToCopyInstrs.clear();