CodeGen: Add DetectDeadLanes pass.

[MatzeB]

Summary

The DetectDeadLanes pass performs a dataflow analysis of used/defined
subregister lanes across COPY instructions and instructions that will
get lowered to copies. It detects dead definitions and uses reading
undefined values which are obscured by COPY and subregister usage.

These dead definitions cause trouble in the register coalescer which
cannot deal with definitions suddenly becoming dead after coalescing
COPY instructions.

For now the pass only adds dead and undef flags to machine operands. It
should be easy to extend it in the future to remove the dead
instructions and redo the analysis for the affected virtual
registers.

[MatzeB]

Note that this patch depends on two small TableGen changes (adding of reverseComposeSubRegIndexLaneMask()) which are simple enough for post-commit review but which I have not pushed yet.

[qcolombet]

Hi Matthias,

This mostly looks good to me with a couple of nitpicks, remarks, and questions.

Cheers,
-Quentin

lib/CodeGen/DetectDeadLanes.cpp

26

How do we end up generating this kind of code?

Although I agree we need to support it, we should try not to generate that.

55

Do not indent namespace:
http://llvm.org/docs/CodingStandards.html#namespace-indentation

I am surprise clang-format do not do the right thing.

58

Shouldn't this be public?

70

Add doxygen comments.

75

Detail what does it mean to transfer the used lanes (BTW, you should use \p for UsedLanes).

91

containing

93

Should we merge those two with like a SmallVectorSet?
Indeed, if I am readying the code correctly, both need to be in sync.

98

Override the getPassName method as well to ease debugging.

109

A remark: since the goal right now is just to fix up the representation for the register coalescer, there is no value in supporting those.
However, if we go toward teaching this pass dead code elimination, then yes, it would make sense to do that.

136

I would have expected the check with InWorkList to be hidden into addToWorklist.

142

Use a switch on the Opcode.

149

What is the benefit of going backward?
I found it confusing to have a "for(;;)" for this traversal.

I would have expected something like:
for (unsigned I = 1, E = MI.getNumOperands(); I != E; I += 2)

175

Add a message in the assert. Like unexpected copy-like instruction.

189

Add a comment why we limit ourselves to instruction with only one def.
For future reference, we need to know if this is a limitation or just that it does not make sense to support more than one definition.

189

What happens with inlineasm?
I.e., we do not get the actual number of definitions via the static description.
Explain why it is okay.

212

Ditto: Check hidden inside addToWorklist.

220

switch for on the opcode

236

Message in assert.

238

The formatting looks weird to me.
I.e., I would have expected clang-format to put the assignment operator on the previous line.

253

The motivating example in the comment at the beginning of the file does not need sub register liveness to produce dead definitions after coalescing, does it?

I.e., is this true we do not need that pass when enableSubRegLiveness is false?

262

For the arrays, wouldn't using plain arrays be more effective?
In particular, we do not iterate on those and having easily access to there length is useless.

306

What does this else block covers?
A register is either virtual or physical, right?

What am I missing?

347

Message in assert.

358

No need for the curly braces.

[MatzeB]

Thanks for the review. Addressed the comments.

lib/CodeGen/DetectDeadLanes.cpp

26

The example here is artificially designed to require a minimum amount of instructions to demonstrate the issue.

It's a good question however where the real issues come from, I'll take a look around.

109

There is still some value as it improves the precision of detecting unused/dead lanes. However from what I can see the ARM target is the only one implementing these instructions and the pass doesn't even run for this target, so I leave the support for this as a future enhancement.

136

Micro optimization because in the initial pass below I can insert without even checking if the value is already in the list. Anyway with the switch to SetVector this point is moot.

149

If the subregister in the REG_SEQUENCE overlap each other (I couldn't find any evidence that this is not allowed), then later operands may override parts of the earlier operands. That's why this loop moves backwards and reduces the UsedLanes bitmask with each operand.

189

At this point we only care about lowersToCopy() instructions. They are the only ones that need subsequent transfer/updating all other operands have been handled in the first pass already.
I added a comment explaining this as the check for the copy-likeness comes later in the form of the !DefinedByCopy[X].

253

This pass does not use any sub-register liveness. My idea here was that it is probably not worth spending the compiletime on this pass for a target that does not even care to enable subregister liveness (though admittedly the pass is quite fast and more powerful than DeadMachineInstrElim because it finds the dataflow fixpoint). You think it is a good idea to enable for all targets, I measured it usually taking around 0.5% compiletime.

306

The operand can also be 0 (aka. "NoRegister"). Added a comment.

[qcolombet]

lib/CodeGen/DetectDeadLanes.cpp

149

I wouldn’t have expected overlaps, but you’re right this is not forbidden.
That being said, this means that we make an assumption on how the register sequence will be broken down and scheduled.

I would rather treat each operand independently and ignore the overlapping but print something in the debug output if the case happens.

253

I know it does not use any sub-register liveness.

What I am saying is without that pass, the coalescer might expose dead defs it was not expecting and cause later crashes.
I.e., if I understood correctly, this pass should always run to avoid potential crashes, right?

306

We usually put the “noreg” case earlier.
In that case, I would have expected this check to be right after getReg().

That being said, I am fine with the current form, it is just unusual :).

[MatzeB]

Change REG_SEQUENCE transfer function to make no assumptions about the order in which subregisters are processed, this is more conservative in the case that the subreg indexes overlap and allows a nicer forward loop.

lib/CodeGen/DetectDeadLanes.cpp

253

Without subregister liveness the coalescer is not able to recognize these dead definitions, so from a correctness perspective we only need the pass for subregister liveness enabled targets.

[qcolombet]

LGTM.

lib/CodeGen/DetectDeadLanes.cpp

255

Great, that is the information I was looking for :).

Add a comment in runOnMachineFunction when we skip the pass to know why it is not run.

[MatzeB]

As the SetVector/BitSet reviews seem to be stalled I will commit a version which directly uses a BitVector+std::deque now.
More testing also revealed that I have to check for cross-class copies which render lanemask information invalid.

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
 
   /// UnreachableMachineBlockElimination - This pass removes unreachable
   /// machine basic blocks.
   extern char &UnreachableMachineBlockElimID;
 
   /// DeadMachineInstructionElim - This pass removes dead machine instructions.
   extern char &DeadMachineInstructionElimID;
 
+  /// This pass adds dead/undef flags after analyzing subregister lanes.
+  extern char &DetectDeadLanesID;
+
   /// FastRegisterAllocation Pass - This pass register allocates as fast as
   /// possible. It is best suited for debug code where live ranges are short.
   ///
   FunctionPass *createFastRegisterAllocator();
 
   /// BasicRegisterAllocation Pass - This pass implements a degenerate global
   /// register allocator using the basic regalloc framework.
   ///

include/llvm/InitializePasses.h

 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCEPass(PassRegistry&);
 void initializeDSEPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDelinearizationPass(PassRegistry &);
 void initializeDependenceAnalysisPass(PassRegistry&);
+void initializeDetectDeadLanesPass(PassRegistry&);
 void initializeDivergenceAnalysisPass(PassRegistry&);
 void initializeDomOnlyPrinterPass(PassRegistry&);
 void initializeDomOnlyViewerPass(PassRegistry&);
 void initializeDomPrinterPass(PassRegistry&);
 void initializeDomViewerPass(PassRegistry&);
 void initializeDominanceFrontierWrapperPassPass(PassRegistry&);
 void initializeDominatorTreeWrapperPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);

lib/CodeGen/CMakeLists.txt

 add_llvm_library(LLVMCodeGen
   AggressiveAntiDepBreaker.cpp
   AllocationOrder.cpp
   Analysis.cpp
   AtomicExpandPass.cpp
   BasicTargetTransformInfo.cpp
   BranchFolding.cpp
   BuiltinGCs.cpp
   CalcSpillWeights.cpp
   CallingConvLower.cpp
   CodeGen.cpp
   CodeGenPrepare.cpp
   CriticalAntiDepBreaker.cpp
   DeadMachineInstructionElim.cpp
+  DetectDeadLanes.cpp
   DFAPacketizer.cpp
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
   EdgeBundles.cpp
   ExecutionDepsFix.cpp
   ExpandISelPseudos.cpp
   ExpandPostRAPseudos.cpp
   FaultMaps.cpp

lib/CodeGen/CodeGen.cpp

 using namespace llvm;
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeAtomicExpandPass(Registry);
   initializeBranchFolderPassPass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeDeadMachineInstructionElimPass(Registry);
+  initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeEarlyIfConverterPass(Registry);
   initializeExpandISelPseudosPass(Registry);
   initializeExpandPostRAPass(Registry);
   initializeFinalizeMachineBundlesPass(Registry);
   initializeFuncletLayoutPass(Registry);
   initializeGCMachineCodeAnalysisPass(Registry);
   initializeGCModuleInfoPass(Registry);

lib/CodeGen/DetectDeadLanes.cpp

+//===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// Analysis that tracks defined/used subregister lanes across COPY instructions
+/// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,
+/// INSERT_SUBREG, EXTRACT_SUBREG).
+/// The information is used to detect dead definitions and the usage of
+/// (completely) undefined values and mark the operands as such.
+/// This pass is necessary because the dead/undef status is not obvious anymore
+/// when subregisters are involved.
+///
+/// Example:
+///    %vreg0 = some definition
+///    %vreg1 = IMPLICIT_DEF
+///    %vreg2 = REG_SEQUENCE %vreg0, sub0, %vreg1, sub1
+///    %vreg3 = EXTRACT_SUBREG %vreg2, sub1
+///           = use %vreg3
+/// The %vreg0 definition is dead and %vreg3 contains an undefined value.
+//
+//===----------------------------------------------------------------------===//
+
+#include <deque>
+#include <vector>
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "detect-dead-lanes"
+
+namespace {
+
+/// Contains a bitmask of which lanes of a given virtual register are
+/// defined and which ones are actually used.
+struct VRegInfo {
+  LaneBitmask UsedLanes;
+  LaneBitmask DefinedLanes;
+};
+
+class DetectDeadLanes : public MachineFunctionPass {
+public:
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  static char ID;
+  DetectDeadLanes() : MachineFunctionPass(ID) {}
+
+  const char *getPassName() const override { return "Detect Dead Lanes"; }
+
+private:
+  /// Add used lane bits on the register used by operand \p MO. This translates
+  /// the bitmask based on the operands subregister, and puts the register into
+  /// the worklist if any new bits were added.
+  void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
+
+  /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
+  /// COPY-like instruction determine the lanes used on the use operands
+  /// and call addUsedLanesOnOperand() for them.
+  void transferUsedLanesStep(const MachineOperand &Def, LaneBitmask UsedLanes);
+
+  /// Given a use regiser operand \p Use and a mask of defined lanes, check
+  /// if the operand belongs to a lowerToCopies() instruction, transfer the
+  /// mask to the def and put the instruction into the worklist.
+  void transferDefinedLanesStep(const MachineOperand &Use,
+                                LaneBitmask DefinedLanes);
+
+  /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
+  /// of COPY-like instruction, determine which lanes are defined at the output
+  /// operand \p Def.
+  LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
+                                   LaneBitmask DefinedLanes);
+
+  const MachineRegisterInfo *MRI;
+  const TargetRegisterInfo *TRI;
+
+  VRegInfo *VRegInfos;
+  /// Worklist containing virtreg indices to process.
+  SetVector<unsigned, std::deque<unsigned>, BitVector> WorkList;
+  /// This bitvector is set for each vreg index where the vreg is defined
+  /// by an instruction where lowersToCopies()==true.
+  BitVector DefinedByCopy;
+};
+
+} // end anonymous namespace
+
+char DetectDeadLanes::ID = 0;
+char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
+
+INITIALIZE_PASS(DetectDeadLanes, "detect-dead-lanes", "Detect Dead Lanes",
+                false, false);
+
+/// Returns true if \p MI will get lowered to a series of COPY instructions.
+/// We call this a COPY-like instruction.
+static bool lowersToCopies(const MachineInstr &MI) {
+  // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
+  // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
+  // are not lowered to a COPY.
+  return MI.isCopy() || MI.isPHI() || MI.isInsertSubreg() ||
+         MI.isRegSequence() || MI.isExtractSubreg();
+}
+
+void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
+                                            LaneBitmask UsedLanes) {
+  if (!MO.readsReg())
+    return;
+  unsigned MOReg = MO.getReg();
+  if (!TargetRegisterInfo::isVirtualRegister(MOReg))
+    return;
+
+  unsigned MOSubReg = MO.getSubReg();
+  if (MOSubReg != 0)
+    UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
+  UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
+
+  unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
+  VRegInfo &MORegInfo = VRegInfos[MORegIdx];
+  LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
+  // Any change at all?
+  if ((UsedLanes & ~PrevUsedLanes) == 0)
+    return;
+
+  // Set UsedLanes and remember instruction for further propagation.
+  MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
+  if (DefinedByCopy[MORegIdx])
+    WorkList.insert(MORegIdx);
+}
+
+void DetectDeadLanes::transferUsedLanesStep(const MachineOperand &Def,
+                                            LaneBitmask UsedLanes) {
+  const MachineInstr &MI = *Def.getParent();
+  switch (MI.getOpcode()) {
+  case TargetOpcode::COPY:
+  case TargetOpcode::PHI:
+    for (const MachineOperand &MO : MI.uses()) {
+      if (MO.isReg() && MO.isUse())
+        addUsedLanesOnOperand(MO, UsedLanes);
+    }
+    break;
+  case TargetOpcode::REG_SEQUENCE: {
+    unsigned I = MI.getNumOperands() - 2;
+    for (;;) {
+      const MachineOperand &MO = MI.getOperand(I);
+      unsigned SubIdx = MI.getOperand(I + 1).getImm();
+      LaneBitmask MOUsedLanes =
+          TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
+
+      addUsedLanesOnOperand(MO, MOUsedLanes);
+
+      LaneBitmask SubIdxMask = TRI->getSubRegIndexLaneMask(SubIdx);
+      UsedLanes &= ~SubIdxMask;
+      if (I == 1)
+        break;
+      I -= 2;
+    }
+    break;
+  }
+  case TargetOpcode::INSERT_SUBREG: {
+    const MachineOperand &MO2 = MI.getOperand(2);
+    unsigned SubIdx = MI.getOperand(3).getImm();
+    LaneBitmask MO2UsedLanes =
+        TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
+    addUsedLanesOnOperand(MO2, MO2UsedLanes);
+
+    const MachineOperand &MO1 = MI.getOperand(1);
+    LaneBitmask MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
+    addUsedLanesOnOperand(MO1, MO1UsedLanes);
+    break;
+  }
+  case TargetOpcode::EXTRACT_SUBREG: {
+    const MachineOperand &MO = MI.getOperand(1);
+    unsigned SubIdx = MI.getOperand(2).getImm();
+    LaneBitmask MOUsedLanes =
+        TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
+    addUsedLanesOnOperand(MO, MOUsedLanes);
+    break;
+  }
+  default:
+    llvm_unreachable("function must be called with COPY-like instruction");
+  }
+}
+
+void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
+                                               LaneBitmask DefinedLanes) {
+  if (!Use.readsReg())
+    return;
+  // Check whether the operand writes a vreg and is part of a COPY-like
+  // instruction.
+  const MachineInstr &MI = *Use.getParent();
+  if (MI.getDesc().getNumDefs() != 1)
+    return;
+  const MachineOperand &Def = *MI.defs().begin();
+  unsigned DefReg = Def.getReg();
+  if (!TargetRegisterInfo::isVirtualRegister(DefReg))
+    return;
+  unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
+  if (!DefinedByCopy[DefRegIdx])
+    return;
+
+  unsigned OpNum = MI.getOperandNo(&Use);
+  DefinedLanes =
+      TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
+  DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
+
+  VRegInfo &RegInfo = VRegInfos[DefRegIdx];
+  LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
+  // Any change at all?
+  if ((DefinedLanes & ~PrevDefinedLanes) == 0)
+    return;
+
+  RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
+  WorkList.insert(DefRegIdx);
+}
+
+LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
+                                                  unsigned OpNum,
+                                                  LaneBitmask DefinedLanes) {
+  const MachineInstr &MI = *Def.getParent();
+  // Translate DefinedLanes if necessary.
+  switch (MI.getOpcode()) {
+  case TargetOpcode::REG_SEQUENCE: {
+    unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
+    DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
+    DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
+    break;
+  }
+  case TargetOpcode::INSERT_SUBREG: {
+    unsigned SubIdx = MI.getOperand(3).getImm();
+    if (OpNum == 2) {
+      DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
+      DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
+    } else {
+      assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
+      // Ignore lanes defined by operand 2.
+      DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
+    }
+    break;
+  }
+  case TargetOpcode::EXTRACT_SUBREG: {
+    unsigned SubIdx = MI.getOperand(2).getImm();
+    assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
+    DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
+    break;
+  }
+  case TargetOpcode::COPY:
+  case TargetOpcode::PHI:
+    break;
+  default:
+    llvm_unreachable("function must be called with COPY-like instruction");
+  }
+
+  unsigned SubIdx = Def.getSubReg();
+  DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
+  DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
+  return DefinedLanes;
+}
+
+bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
+  // Don't bother if we won't track subregister liveness later.
+  if (!MF.getSubtarget().enableSubRegLiveness()) {
+    DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
+    return false;
+  }
+
+  MRI = &MF.getRegInfo();
+  TRI = MRI->getTargetRegisterInfo();
+
+  unsigned NumVirtRegs = MRI->getNumVirtRegs();
+  VRegInfos = new VRegInfos[NumVirtRegs];
+  WorkList.resize(NumVirtRegs);
+  DefinedByCopy.resize(NumVirtRegs);
+
+  // First pass: Populate defs/uses of vregs with initial values
+  for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
+    VRegInfo &Info = VRegInfos[RegIdx];
+    // Ignore special vregs without a definition and vregs where we won't track
+    // subregister liveness anyway.
+    if (!MRI->hasOneDef(Reg)) {
+      Info.UsedLanes = ~0u;
+      Info.DefinedLanes = ~0u;
+      continue;
+    }
+
+    const MachineOperand &Def = *MRI->def_begin(Reg);
+    const MachineInstr &DefMI = *Def.getParent();
+    LaneBitmask DefinedLanes;
+    if (lowersToCopies(DefMI)) {
+      // Start optimisatically with no used or defined lanes for copy
+      // instructions. The following dataflow analysis will add more bits.
+      DefinedLanes = 0;
+      DefinedByCopy.set(RegIdx);
+
+      // Determine initially DefinedLanes.
+      for (const MachineOperand &MO : DefMI.uses()) {
+        if (!MO.isReg() || !MO.readsReg())
+          continue;
+        unsigned MOReg = MO.getReg();
+        LaneBitmask MODefinedLanes;
+        if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
+          if (MRI->hasOneDef(MOReg)) {
+            const MachineOperand &MODef = *MRI->def_begin(MOReg);
+            const MachineInstr &MODefMI = *MODef.getParent();
+            // Bits from copy-like operations will be added later.
+            if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
+              continue;
+          }
+          MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
+          MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
+              MO.getSubReg(), MODefinedLanes);
+        } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
+          MODefinedLanes = ~0u;
+        } else {
+          // "NoRegister".
+          continue;
+        }
+
+        unsigned OpNum = DefMI.getOperandNo(&MO);
+        DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
+      }
+
+      WorkList.insert(RegIdx);
+    } else if (DefMI.isImplicitDef()) {
+      DefinedLanes = 0;
+    } else {
+      unsigned SubReg = Def.getSubReg();
+      DefinedLanes = SubReg != 0 ? TRI->getSubRegIndexLaneMask(SubReg)
+                                 : MRI->getMaxLaneMaskForVReg(Reg);
+    }
+
+    LaneBitmask UsedLanes = 0;
+    for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
+      if (MO.isUndef() || MO.isInternalRead())
+        continue;
+
+      const MachineInstr &UseMI = *MO.getParent();
+      if (UseMI.isKill())
+        continue;
+      if (lowersToCopies(UseMI)) {
+        assert(UseMI.getDesc().getNumDefs() == 1);
+        const MachineOperand &Def = *UseMI.defs().begin();
+        if (TargetRegisterInfo::isVirtualRegister(Def.getReg()))
+          continue;
+      }
+
+      unsigned SubReg = MO.getSubReg();
+      if (SubReg == 0) {
+        UsedLanes = MRI->getMaxLaneMaskForVReg(Reg);
+        // Shortcut: All lanes are already set.
+        break;
+      }
+      UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
+    }
+    Info.UsedLanes = UsedLanes;
+    Info.DefinedLanes = DefinedLanes;
+  }
+
+  // Iterate as long as defined lanes/used lanes keep changing.
+  while (!WorkList.empty()) {
+    unsigned RegIdx = WorkList.pop_front_val();
+    VRegInfo &Info = VRegInfos[RegIdx];
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
+
+    // Transfer UsedLanes to operands of DefMI (backwards dataflow).
+    MachineOperand &Def = *MRI->def_begin(Reg);
+    transferUsedLanesStep(Def, Info.UsedLanes);
+    // Transfer DefinedLanes to users of Reg (forward dataflow).
+    for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
+      transferDefinedLanesStep(MO, Info.DefinedLanes);
+  }
+
+  DEBUG(
+    dbgs() << "Defined/Used lanes:\n";
+    for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
+      unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
+      const VRegInfo &Info = VRegInfos[RegIdx];
+      dbgs() << PrintReg(Reg, nullptr)
+             << " Used: " << PrintLaneMask(Info.UsedLanes)
+             << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
+    }
+    dbgs() << "\n";
+  );
+
+  // Mark operands as dead/unused.
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      for (MachineOperand &MO : MI.operands()) {
+        if (!MO.isReg())
+          continue;
+        unsigned Reg = MO.getReg();
+        if (!TargetRegisterInfo::isVirtualRegister(Reg))
+          continue;
+        unsigned SubReg = MO.getSubReg();
+        LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
+        unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
+        const VRegInfo &RegInfo = VRegInfos[RegIdx];
+        if (MO.isDef() && RegInfo.UsedLanes == 0) {
+          DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
+          MO.setIsDead();
+        } else if (MO.readsReg() && (RegInfo.DefinedLanes & Mask) == 0) {
+          DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in " << MI);
+          MO.setIsUndef();
+        }
+      }
+    }
+  }
+
+  DefinedByCopy.clear();
+  WorkList.clear();
+  delete[] VRegInfos;
+  return true;
+}

lib/CodeGen/Passes.cpp

void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
   if (RegAllocPass)
     addPass(RegAllocPass);
 }
 
 /// Add standard target-independent passes that are tightly coupled with
 /// optimized register allocation, including coalescing, machine instruction
 /// scheduling, and register allocation itself.
 void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
+  addPass(&DetectDeadLanesID, false);
+
   addPass(&ProcessImplicitDefsID, false);
 
   // LiveVariables currently requires pure SSA form.
   //
   // FIXME: Once TwoAddressInstruction pass no longer uses kill flags,
   // LiveVariables can be removed completely, and LiveIntervals can be directly
   // computed. (We still either need to regenerate kill flags after regalloc, or
   // preferably fix the scavenger to not depend on them).

test/CodeGen/AMDGPU/detect-dead-lanes.mir

+# RUN: llc -march=amdgcn -run-pass detect-dead-lanes -o /dev/null %s 2>&1 | FileCheck %s
+--- |
+  define void @test0() { ret void }
+  define void @test1() { ret void }
+  define void @test2() { ret void }
+  define void @test3() { ret void }
+  define void @test4() { ret void }
+  define void @loop0() { ret void }
+  define void @loop1() { ret void }
+  define void @loop2() { ret void }
+...
+---
+# Combined use/def transfer check, the basics.
+# CHECK-LABEL: name: test0
+# CHECK: S_NOP 0, implicit-def %0
+# CHECK: S_NOP 0, implicit-def %1
+# CHECK: S_NOP 0, implicit-def dead %2
+# CHECK: %3 = REG_SEQUENCE %0, {{[0-9]+}}, %1, {{[0-9]+}}, %2, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %3:sub0
+# CHECK: S_NOP 0, implicit %3:sub1
+# CHECK: S_NOP 0, implicit undef %3:sub2
+# CHECK: %4 = COPY %3:sub0_sub1
+# CHECK: %5 = COPY %3:sub2_sub3
+# CHECK: S_NOP 0, implicit %4:sub0
+# CHECK: S_NOP 0, implicit %4:sub1
+# CHECK: S_NOP 0, implicit undef %5:sub0
+name: test0
+isSSA: true
+registers:
+  - { id: 0, class: sreg_32 }
+  - { id: 1, class: sreg_32 }
+  - { id: 2, class: sreg_32 }
+  - { id: 3, class: sreg_128 }
+  - { id: 4, class: sreg_64 }
+  - { id: 5, class: sreg_64 }
+body: |
+  bb.0:
+    S_NOP 0, implicit-def %0
+    S_NOP 0, implicit-def %1
+    S_NOP 0, implicit-def %2
+    %3 = REG_SEQUENCE %0, %subreg.sub0, %1, %subreg.sub1, %2, %subreg.sub3
+    S_NOP 0, implicit %3:sub0
+    S_NOP 0, implicit %3:sub1
+    S_NOP 0, implicit %3:sub2
+    %4 = COPY %3:sub0_sub1
+    %5 = COPY %3:sub2_sub3
+    S_NOP 0, implicit %4:sub0
+    S_NOP 0, implicit %4:sub1
+    S_NOP 0, implicit %5:sub0
+...
+---
+# Check defined lanes transfer; Includes checking for some special cases like
+# undef operands or IMPLICIT_DEF definitions.
+# CHECK-LABEL: name: test1
+# CHECK: %0 = REG_SEQUENCE %sgpr0, {{[0-9]+}}, %sgpr0, {{[0-9]+}}
+# CHECK: %1 = INSERT_SUBREG %0, %sgpr1, {{[0-9]+}}
+# CHECK: %2 = INSERT_SUBREG %0:sub2_sub3, %sgpr42, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %1:sub0
+# CHECK: S_NOP 0, implicit undef %1:sub1
+# CHECK: S_NOP 0, implicit %1:sub2
+# CHECK: S_NOP 0, implicit %1:sub3
+# CHECK: S_NOP 0, implicit %2:sub0
+# CHECK: S_NOP 0, implicit undef %2:sub1
+
+# CHECK: %3 = IMPLICIT_DEF
+# CHECK: %4 = INSERT_SUBREG %0, undef %3, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit undef %4:sub0
+# CHECK: S_NOP 0, implicit undef %4:sub1
+# CHECK: S_NOP 0, implicit %4:sub2
+# CHECK: S_NOP 0, implicit undef %4:sub3
+
+# CHECK: %5 = EXTRACT_SUBREG %0, {{[0-9]+}}
+# CHECK: %6 = EXTRACT_SUBREG %5, {{[0-9]+}}
+# CHECK: %7 = EXTRACT_SUBREG %5, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %5
+# CHECK: S_NOP 0, implicit %6
+# CHECK: S_NOP 0, implicit undef %7
+
+# CHECK: %8 = IMPLICIT_DEF
+# CHECK: %9 = EXTRACT_SUBREG undef %8, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit undef %9
+
+# CHECK: %10 = EXTRACT_SUBREG undef %0, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit undef %10
+name: test1
+isSSA: true
+registers:
+  - { id: 0, class: sreg_128 }
+  - { id: 1, class: sreg_128 }
+  - { id: 2, class: sreg_64 }
+  - { id: 3, class: sreg_32 }
+  - { id: 4, class: sreg_128 }
+  - { id: 5, class: sreg_64 }
+  - { id: 6, class: sreg_32 }
+  - { id: 7, class: sreg_32 }
+  - { id: 8, class: sreg_64 }
+  - { id: 9, class: sreg_32 }
+  - { id: 10, class: sreg_128 }
+body: |
+  bb.0:
+    %0 = REG_SEQUENCE %sgpr0, %subreg.sub0, %sgpr0, %subreg.sub2
+    %1 = INSERT_SUBREG %0, %sgpr1, %subreg.sub3
+    %2 = INSERT_SUBREG %0:sub2_sub3, %sgpr42, %subreg.sub0
+    S_NOP 0, implicit %1:sub0
+    S_NOP 0, implicit %1:sub1
+    S_NOP 0, implicit %1:sub2
+    S_NOP 0, implicit %1:sub3
+    S_NOP 0, implicit %2:sub0
+    S_NOP 0, implicit %2:sub1
+
+    %3 = IMPLICIT_DEF
+    %4 = INSERT_SUBREG %0, %3, %subreg.sub0
+    S_NOP 0, implicit %4:sub0
+    S_NOP 0, implicit %4:sub1
+    S_NOP 0, implicit %4:sub2
+    S_NOP 0, implicit %4:sub3
+
+    %5 = EXTRACT_SUBREG %0, %subreg.sub0_sub1
+    %6 = EXTRACT_SUBREG %5, %subreg.sub0
+    %7 = EXTRACT_SUBREG %5, %subreg.sub1
+    S_NOP 0, implicit %5
+    S_NOP 0, implicit %6
+    S_NOP 0, implicit %7
+
+    %8 = IMPLICIT_DEF
+    %9 = EXTRACT_SUBREG %8, %subreg.sub1
+    S_NOP 0, implicit %9
+
+    %10 = EXTRACT_SUBREG undef %0, %subreg.sub2_sub3
+    S_NOP 0, implicit %10
+...
+---
+# Check used lanes transfer; Includes checking for some special cases like
+# undef operands.
+# CHECK-LABEL: name: test2
+# CHECK: S_NOP 0, implicit-def dead %0
+# CHECK: S_NOP 0, implicit-def %1
+# CHECK: S_NOP 0, implicit-def %2
+# CHECK: %3 = REG_SEQUENCE %0, {{[0-9]+}}, %1, {{[0-9]+}}, %2, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %3:sub1
+# CHECK: S_NOP 0, implicit %3:sub3
+
+# CHECK: S_NOP 0, implicit-def dead %4
+# CHECK: S_NOP 0, implicit-def %5
+# CHECK: %6 = REG_SEQUENCE %4, {{[0-9]+}}, %5, {{[0-9]+}}, %5, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %6
+
+# CHECK: S_NOP 0, implicit-def %7
+# CHECK: S_NOP 0, implicit-def dead %8
+# CHECK: %9 = REG_SEQUENCE %7, {{[0-9]+}}, undef %8, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %9
+
+# CHECK: S_NOP 0, implicit-def dead %10
+# CHECK: S_NOP 0, implicit-def %11
+# CHECK: %12 = INSERT_SUBREG %10, %11, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %12:sub2
+
+# CHECK: S_NOP 0, implicit-def %13
+# CHECK: S_NOP 0, implicit-def dead %14
+# CHECK: %15 = INSERT_SUBREG %13, %14, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %15:sub3
+
+# CHECK: S_NOP 0, implicit-def %16
+# CHECK: S_NOP 0, implicit-def dead %17
+# CHECK: %18 = REG_SEQUENCE %16, {{[0-9]+}}, %17, {{[0-9]+}}
+# CHECK: %19 = EXTRACT_SUBREG %18, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %19:sub1
+
+name: test2
+isSSA: true
+registers:
+  - { id: 0, class: sreg_32 }
+  - { id: 1, class: sreg_32 }
+  - { id: 2, class: sreg_64 }
+  - { id: 3, class: sreg_128 }
+  - { id: 4, class: sreg_32 }
+  - { id: 5, class: sreg_32 }
+  - { id: 6, class: sreg_64 }
+  - { id: 7, class: sreg_32 }
+  - { id: 8, class: sreg_32 }
+  - { id: 9, class: sreg_64 }
+  - { id: 10, class: sreg_128 }
+  - { id: 11, class: sreg_64 }
+  - { id: 12, class: sreg_128 }
+  - { id: 13, class: sreg_128 }
+  - { id: 14, class: sreg_64 }
+  - { id: 15, class: sreg_128 }
+  - { id: 16, class: sreg_64 }
+  - { id: 17, class: sreg_64 }
+  - { id: 18, class: sreg_128 }
+  - { id: 19, class: sreg_64 }
+body: |
+  bb.0:
+    S_NOP 0, implicit-def %0
+    S_NOP 0, implicit-def %1
+    S_NOP 0, implicit-def %2
+    %3 = REG_SEQUENCE %0, %subreg.sub0, %1, %subreg.sub1, %2, %subreg.sub2_sub3
+    S_NOP 0, implicit %3:sub1
+    S_NOP 0, implicit %3:sub3
+
+    S_NOP 0, implicit-def %4
+    S_NOP 0, implicit-def %5
+    %6 = REG_SEQUENCE %4, %subreg.sub0, %5, %subreg.sub1, %5, %subreg.sub0
+    S_NOP 0, implicit %6
+
+    S_NOP 0, implicit-def %7
+    S_NOP 0, implicit-def %8
+    %9 = REG_SEQUENCE %7, %subreg.sub0, undef %8, %subreg.sub1
+    S_NOP 0, implicit %9
+
+    S_NOP 0, implicit-def %10
+    S_NOP 0, implicit-def %11
+    %12 = INSERT_SUBREG %10, %11, %subreg.sub2_sub3
+    S_NOP 0, implicit %12:sub2
+
+    S_NOP 0, implicit-def %13
+    S_NOP 0, implicit-def %14
+    %15 = INSERT_SUBREG %13, %14, %subreg.sub0_sub1
+    S_NOP 0, implicit %15:sub3
+
+    S_NOP 0, implicit-def %16
+    S_NOP 0, implicit-def %17
+    %18 = REG_SEQUENCE %16, %subreg.sub0_sub1, %17, %subreg.sub2_sub3
+    %19 = EXTRACT_SUBREG %18, %subreg.sub0_sub1
+    S_NOP 0, implicit %19:sub1
+...
+---
+# Check that copies to physregs use all lanes, copies from physregs define all
+# lanes. So we should not get a dead/undef flag here.
+# CHECK-LABEL: name: test3
+# CHECK: S_NOP 0, implicit-def %0
+# CHECK: %vcc = COPY %0
+# CHECK: %1 = COPY %vcc
+# CHECK: S_NOP 0, implicit %1
+name: test3
+isSSA: true
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_64 }
+  - { id: 1, class: sreg_64 }
+body: |
+  bb.0:
+    S_NOP 0, implicit-def %0
+    %vcc = COPY %0
+
+    %1 = COPY %vcc
+    S_NOP 0, implicit %1
+...
+---
+# Check that implicit-def/kill do not count as def/uses.
+# CHECK-LABEL: name: test4
+# CHECK: S_NOP 0, implicit-def dead %0
+# CHECK: KILL %0
+# CHECK: %1 = IMPLICIT_DEF
+# CHECK: S_NOP 0, implicit undef %1
+name: test4
+isSSA: true
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_64 }
+  - { id: 1, class: sreg_64 }
+body: |
+  bb.0:
+    S_NOP 0, implicit-def %0
+    KILL %0
+
+    %1 = IMPLICIT_DEF
+    S_NOP 0, implicit %1
+...
+---
+# Check "optimistic" dataflow fixpoint in phi-loops.
+# CHECK-LABEL: name: loop0
+# CHECK: bb.0:
+# CHECK: S_NOP 0, implicit-def %0
+# CHECK: S_NOP 0, implicit-def dead %1
+# CHECK: S_NOP 0, implicit-def dead %2
+# CHECK: %3 = REG_SEQUENCE %0, {{[0-9]+}}, %1, {{[0-9]+}}, %2, {{[0-9]+}}
+
+# CHECK: bb.1:
+# CHECK: %4 = PHI %3, %bb.0, %5, %bb.1
+
+# CHECK: bb.2:
+# CHECK:   S_NOP 0, implicit %4:sub0
+# CHECK:   S_NOP 0, implicit undef %4:sub3
+name: loop0
+isSSA: true
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_32 }
+  - { id: 1, class: sreg_32 }
+  - { id: 2, class: sreg_32 }
+  - { id: 3, class: sreg_128 }
+  - { id: 4, class: sreg_128 }
+  - { id: 5, class: sreg_128 }
+body: |
+  bb.0:
+    successors: %bb.1
+    S_NOP 0, implicit-def %0
+    S_NOP 0, implicit-def %1
+    S_NOP 0, implicit-def %2
+    %3 = REG_SEQUENCE %0, %subreg.sub0, %1, %subreg.sub1, %2, %subreg.sub2
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+    %4 = PHI %3, %bb.0, %5, %bb.1
+
+    ; let's swiffle some lanes around for fun...
+    %5 = REG_SEQUENCE %4:sub0, %subreg.sub0, %4:sub2, %subreg.sub1, %4:sub1, %subreg.sub2, %4:sub3, %subreg.sub3
+
+    S_CBRANCH_VCCNZ %bb.1, implicit undef %vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_NOP 0, implicit %4:sub0
+    S_NOP 0, implicit %4:sub3
+...
+---
+# Check a loop that needs to be traversed multiple times to reach the fixpoint
+# for the used lanes. The example reads sub3 lane at the end, however with each
+# loop iteration we should get 1 more lane marked as we cycles the sublanes
+# along. Sublanes sub0, sub1 and sub3 are rotate in the loop so only sub2
+# should be dead.
+# CHECK-LABEL: name: loop1
+# CHECK: bb.0:
+# CHECK: S_NOP 0, implicit-def %0
+# CHECK: S_NOP 0, implicit-def %1
+# CHECK: S_NOP 0, implicit-def dead %2
+# CHECK: S_NOP 0, implicit-def %3
+# CHECK: %4 = REG_SEQUENCE %0, {{[0-9]+}}, %1, {{[0-9]+}}, %2, {{[0-9]+}}, %3, {{[0-9]+}}
+
+# CHECK: bb.1:
+# CHECK: %5 = PHI %4, %bb.0, %6, %bb.1
+
+# CHECK: %6 = REG_SEQUENCE %5:sub1, {{[0-9]+}}, %5:sub3, {{[0-9]+}}, %5:sub2, {{[0-9]+}}, %5:sub0, {{[0-9]+}}
+
+# CHECK: bb.2:
+# CHECK:   S_NOP 0, implicit %6:sub3
+name: loop1
+isSSA: true
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_32 }
+  - { id: 1, class: sreg_32 }
+  - { id: 2, class: sreg_32 }
+  - { id: 3, class: sreg_32 }
+  - { id: 4, class: sreg_128 }
+  - { id: 5, class: sreg_128 }
+  - { id: 6, class: sreg_128 }
+body: |
+  bb.0:
+    successors: %bb.1
+    S_NOP 0, implicit-def %0
+    S_NOP 0, implicit-def %1
+    S_NOP 0, implicit-def dead %2
+    S_NOP 0, implicit-def %3
+    %4 = REG_SEQUENCE %0, %subreg.sub0, %1, %subreg.sub1, %2, %subreg.sub2, %3, %subreg.sub3
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+    %5 = PHI %4, %bb.0, %6, %bb.1
+
+    ; rotate lanes, but skip sub2 lane...
+    %6 = REG_SEQUENCE %5:sub1, %subreg.sub0, %5:sub3, %subreg.sub1, %5:sub2, %subreg.sub2, %5:sub0, %subreg.sub3
+
+    S_CBRANCH_VCCNZ %bb.1, implicit undef %vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_NOP 0, implicit %6:sub3
+...
+---
+# Similar to loop1 test, but check for fixpoint of defined lanes.
+# Lanes are rotate between sub0, sub2, sub3 so only sub1 should be dead/undef.
+# CHECK-LABEL: name: loop2
+# CHECK: bb.0:
+# CHECK: S_NOP 0, implicit-def %0
+# CHECK: %1 = REG_SEQUENCE %0, {{[0-9]+}}
+
+# CHECK: bb.1:
+# CHECK: %2 = PHI %1, %bb.0, %3, %bb.1
+
+# CHECK: %3 = REG_SEQUENCE %2:sub3, {{[0-9]+}}, undef %2:sub1, {{[0-9]+}}, %2:sub0, {{[0-9]+}}, %2:sub2, {{[0-9]+}}
+
+# CHECK: bb.2:
+# CHECK:   S_NOP 0, implicit %2:sub0
+# CHECK:   S_NOP 0, implicit undef %2:sub1
+# CHECK:   S_NOP 0, implicit %2:sub2
+# CHECK:   S_NOP 0, implicit %2:sub3
+name: loop2
+isSSA: true
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_32 }
+  - { id: 1, class: sreg_128 }
+  - { id: 2, class: sreg_128 }
+  - { id: 3, class: sreg_128 }
+body: |
+  bb.0:
+    successors: %bb.1
+    S_NOP 0, implicit-def %0
+    %1 = REG_SEQUENCE %0, %subreg.sub0
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+    %2 = PHI %1, %bb.0, %3, %bb.1
+
+    ; rotate subreg lanes, skipping sub1
+    %3 = REG_SEQUENCE %2:sub3, %subreg.sub0, %2:sub1, %subreg.sub1, %2:sub0, %subreg.sub2, %2:sub2, %subreg.sub3
+
+    S_CBRANCH_VCCNZ %bb.1, implicit undef %vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_NOP 0, implicit %2:sub0
+    S_NOP 0, implicit undef %2:sub1
+    S_NOP 0, implicit %2:sub2
+    S_NOP 0, implicit %2:sub3
+...