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

25 ↗

(On Diff #51508)

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.

54 ↗

(On Diff #51508)

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

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

57 ↗

(On Diff #51508)

Shouldn't this be public?

69 ↗

(On Diff #51508)

Add doxygen comments.

74 ↗

(On Diff #51508)

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

90 ↗

(On Diff #51508)

containing

92 ↗

(On Diff #51508)

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

97 ↗

(On Diff #51508)

Override the getPassName method as well to ease debugging.

108 ↗

(On Diff #51508)

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.

135 ↗

(On Diff #51508)

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

141 ↗

(On Diff #51508)

Use a switch on the Opcode.

148 ↗

(On Diff #51508)

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)

174 ↗

(On Diff #51508)

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

188 ↗

(On Diff #51508)

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.

188 ↗

(On Diff #51508)

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

211 ↗

(On Diff #51508)

Ditto: Check hidden inside addToWorklist.

219 ↗

(On Diff #51508)

switch for on the opcode

235 ↗

(On Diff #51508)

Message in assert.

237 ↗

(On Diff #51508)

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

252 ↗

(On Diff #51508)

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?

261 ↗

(On Diff #51508)

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.

305 ↗

(On Diff #51508)

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

What am I missing?

346 ↗

(On Diff #51508)

Message in assert.

357 ↗

(On Diff #51508)

No need for the curly braces.

[MatzeB]

Thanks for the review. Addressed the comments.

lib/CodeGen/DetectDeadLanes.cpp

25 ↗

(On Diff #51508)

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.

108 ↗

(On Diff #51508)

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.

135 ↗

(On Diff #51508)

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.

148 ↗

(On Diff #51508)

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.

188 ↗

(On Diff #51508)

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].

252 ↗

(On Diff #51508)

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.

305 ↗

(On Diff #51508)

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

[qcolombet]

lib/CodeGen/DetectDeadLanes.cpp

149 ↗

(On Diff #51990)

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 ↗

(On Diff #51990)

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 ↗

(On Diff #51990)

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 ↗

(On Diff #51990)

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

254 ↗

(On Diff #52006)

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.

llvm/trunk/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.
   ///

llvm/trunk/include/llvm/InitializePasses.h

 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(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&);

llvm/trunk/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

llvm/trunk/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);

llvm/trunk/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/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);
+
+  LaneBitmask determineInitialDefinedLanes(unsigned Reg);
+  LaneBitmask determineInitialUsedLanes(unsigned Reg);
+
+  const MachineRegisterInfo *MRI;
+  const TargetRegisterInfo *TRI;
+
+  void PutInWorklist(unsigned RegIdx) {
+    if (WorklistMembers.test(RegIdx))
+      return;
+    WorklistMembers.set(RegIdx);
+    Worklist.push_back(RegIdx);
+  }
+
+  VRegInfo *VRegInfos;
+  /// Worklist containing virtreg indexes.
+  std::deque<unsigned> Worklist;
+  BitVector WorklistMembers;
+  /// 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.
+  switch (MI.getOpcode()) {
+  case TargetOpcode::COPY:
+  case TargetOpcode::PHI:
+  case TargetOpcode::INSERT_SUBREG:
+  case TargetOpcode::REG_SEQUENCE:
+  case TargetOpcode::EXTRACT_SUBREG:
+    return true;
+  }
+  return false;
+}
+
+static bool isCrossCopy(const MachineRegisterInfo &MRI,
+                        const MachineInstr &MI,
+                        const TargetRegisterClass *DstRC,
+                        const MachineOperand &MO) {
+  assert(lowersToCopies(MI));
+  unsigned SrcReg = MO.getReg();
+  const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
+  if (DstRC == SrcRC)
+    return false;
+
+  unsigned SrcSubIdx = MO.getSubReg();
+
+  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
+  unsigned DstSubIdx = 0;
+  switch (MI.getOpcode()) {
+  case TargetOpcode::INSERT_SUBREG:
+    if (MI.getOperandNo(&MO) == 2)
+      DstSubIdx = MI.getOperand(3).getImm();
+    break;
+  case TargetOpcode::REG_SEQUENCE: {
+    unsigned OpNum = MI.getOperandNo(&MO);
+    DstSubIdx = MI.getOperand(OpNum+1).getImm();
+    break;
+  }
+  case TargetOpcode::EXTRACT_SUBREG: {
+    unsigned SubReg = MI.getOperand(2).getImm();
+    SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
+  }
+  }
+
+  unsigned PreA, PreB; // Unused.
+  if (SrcSubIdx && DstSubIdx)
+    return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
+                                       PreB);
+  if (SrcSubIdx)
+    return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
+  if (DstSubIdx)
+    return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
+  return !TRI.getCommonSubClass(SrcRC, DstRC);
+}
+
+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.test(MORegIdx))
+    PutInWorklist(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: {
+    // Note: This loop makes the conservative assumption that subregister
+    // indices do not overlap or that we do not know how the overlap is
+    // resolved when lowering to copies.
+    for (unsigned I = 1, N = MI.getNumOperands(); I < N; I += 2) {
+      const MachineOperand &MO = MI.getOperand(I);
+      unsigned SubIdx = MI.getOperand(I + 1).getImm();
+      LaneBitmask MOUsedLanes =
+          TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
+
+      addUsedLanesOnOperand(MO, MOUsedLanes);
+    }
+    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);
+    unsigned DefReg = Def.getReg();
+    const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
+    LaneBitmask MO1UsedLanes;
+    if (RC->CoveredBySubRegs)
+      MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
+    else
+      MO1UsedLanes = RC->LaneMask;
+    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;
+  // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
+  // they really need to be modeled differently!
+  if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
+    return;
+  const MachineOperand &Def = *MI.defs().begin();
+  unsigned DefReg = Def.getReg();
+  if (!TargetRegisterInfo::isVirtualRegister(DefReg))
+    return;
+  unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
+  if (!DefinedByCopy.test(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;
+  PutInWorklist(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;
+}
+
+LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
+  // Live-In or unused registers have no definition but are considered fully
+  // defined.
+  if (!MRI->hasOneDef(Reg))
+    return ~0u;
+
+  const MachineOperand &Def = *MRI->def_begin(Reg);
+  const MachineInstr &DefMI = *Def.getParent();
+  if (lowersToCopies(DefMI)) {
+    // Start optimisatically with no used or defined lanes for copy
+    // instructions. The following dataflow analysis will add more bits.
+    unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
+    DefinedByCopy.set(RegIdx);
+    PutInWorklist(RegIdx);
+
+    if (Def.isDead())
+      return 0;
+
+    // COPY/PHI can copy across unrelated register classes (example: float/int)
+    // with incompatible subregister structure. Do not include these in the
+    // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
+    const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
+
+    // Determine initially DefinedLanes.
+    LaneBitmask DefinedLanes = 0;
+    for (const MachineOperand &MO : DefMI.uses()) {
+      if (!MO.isReg() || !MO.readsReg())
+        continue;
+      unsigned MOReg = MO.getReg();
+      if (!MOReg)
+        continue;
+
+      LaneBitmask MODefinedLanes;
+      if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
+        MODefinedLanes = ~0u;
+      } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
+        MODefinedLanes = ~0u;
+      } else {
+        assert(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;
+        }
+        unsigned MOSubReg = MO.getSubReg();
+        MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
+        MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
+            MOSubReg, MODefinedLanes);
+      }
+
+      unsigned OpNum = DefMI.getOperandNo(&MO);
+      DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
+    }
+    return DefinedLanes;
+  }
+  if (DefMI.isImplicitDef() || Def.isDead())
+    return 0;
+
+  unsigned SubReg = Def.getSubReg();
+  return SubReg != 0 ? TRI->getSubRegIndexLaneMask(SubReg)
+                     : MRI->getMaxLaneMaskForVReg(Reg);
+}
+
+LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
+  LaneBitmask UsedLanes = 0;
+  for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
+    if (!MO.readsReg())
+      continue;
+
+    const MachineInstr &UseMI = *MO.getParent();
+    if (UseMI.isKill())
+      continue;
+
+    unsigned SubReg = MO.getSubReg();
+    if (lowersToCopies(UseMI)) {
+      assert(UseMI.getDesc().getNumDefs() == 1);
+      const MachineOperand &Def = *UseMI.defs().begin();
+      unsigned DefReg = Def.getReg();
+      // The used lanes of COPY-like instruction operands are determined by the
+      // following dataflow analysis.
+      if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
+        // But ignore copies across incompatible register classes.
+        bool CrossCopy = false;
+        if (lowersToCopies(UseMI)) {
+          const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
+          CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
+        }
+
+        if (!CrossCopy)
+          continue;
+      }
+    }
+
+    // Shortcut: All lanes are used.
+    if (SubReg == 0)
+      return MRI->getMaxLaneMaskForVReg(Reg);
+
+    UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
+  }
+  return UsedLanes;
+}
+
+bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
+  // Don't bother if we won't track subregister liveness later.  This pass is
+  // required for correctness if subregister liveness is enabled because the
+  // register coalescer cannot deal with hidden dead defs. However without
+  // subregister liveness enabled, the expected benefits of this pass are small
+  // so we safe the compile time.
+  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 VRegInfo[NumVirtRegs];
+  WorklistMembers.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);
+
+    // Determine used/defined lanes and add copy instructions to worklist.
+    VRegInfo &Info = VRegInfos[RegIdx];
+    Info.DefinedLanes = determineInitialDefinedLanes(Reg);
+    Info.UsedLanes = determineInitialUsedLanes(Reg);
+  }
+
+  // Iterate as long as defined lanes/used lanes keep changing.
+  while (!Worklist.empty()) {
+    unsigned RegIdx = Worklist.front();
+    Worklist.pop_front();
+    WorklistMembers.reset(RegIdx);
+    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 (RegInfo.UsedLanes == 0 && MO.isDef() && !MO.isDead()) {
+          DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
+          MO.setIsDead();
+        }
+        if (((RegInfo.UsedLanes & Mask) == 0 ||
+             (RegInfo.DefinedLanes & Mask) == 0) && MO.readsReg()) {
+          DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in " << MI);
+          MO.setIsUndef();
+        }
+      }
+    }
+  }
+
+  DefinedByCopy.clear();
+  WorklistMembers.clear();
+  delete[] VRegInfos;
+  return true;
+}

llvm/trunk/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).

llvm/trunk/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]+}}, undef %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 undef %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 %4
+# CHECK: S_NOP 0, implicit-def dead %5
+# CHECK: %6 = REG_SEQUENCE %4, {{[0-9]+}}, undef %5, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %6
+
+# CHECK: S_NOP 0, implicit-def dead %7
+# CHECK: S_NOP 0, implicit-def %8
+# CHECK: %9 = INSERT_SUBREG undef %7, %8, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %9:sub2
+
+# CHECK: S_NOP 0, implicit-def %10
+# CHECK: S_NOP 0, implicit-def dead %11
+# CHECK: %12 = INSERT_SUBREG %10, undef %11, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %12:sub3
+
+# CHECK: S_NOP 0, implicit-def %13
+# CHECK: S_NOP 0, implicit-def dead %14
+# CHECK: %15 = REG_SEQUENCE %13, {{[0-9]+}}, undef %14, {{[0-9]+}}
+# CHECK: %16 = EXTRACT_SUBREG %15, {{[0-9]+}}
+# CHECK: S_NOP 0, implicit %16: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_128 }
+  - { id: 8, class: sreg_64 }
+  - { id: 9, class: sreg_128 }
+  - { id: 10, class: sreg_128 }
+  - { id: 11, class: sreg_64 }
+  - { id: 12, class: sreg_128 }
+  - { id: 13, class: sreg_64 }
+  - { id: 14, class: sreg_64 }
+  - { id: 15, class: sreg_128 }
+  - { id: 16, 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, undef %5, %subreg.sub1
+    S_NOP 0, implicit %6
+
+    S_NOP 0, implicit-def %7
+    S_NOP 0, implicit-def %8
+    %9 = INSERT_SUBREG %7, %8, %subreg.sub2_sub3
+    S_NOP 0, implicit %9:sub2
+
+    S_NOP 0, implicit-def %10
+    S_NOP 0, implicit-def %11
+    %12 = INSERT_SUBREG %10, %11, %subreg.sub0_sub1
+    S_NOP 0, implicit %12:sub3
+
+    S_NOP 0, implicit-def %13
+    S_NOP 0, implicit-def %14
+    %15 = REG_SEQUENCE %13, %subreg.sub0_sub1, %14, %subreg.sub2_sub3
+    %16 = EXTRACT_SUBREG %15, %subreg.sub0_sub1
+    S_NOP 0, implicit %16: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 undef %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]+}}, undef %1, {{[0-9]+}}, undef %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]+}}, undef %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]+}}, undef %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
+...